Computer Architecture


## Intro

우리가 원하는 것은 강한 performance를 발휘하면서도, 가용성(availability, 끊김 없이 사용할 수 있는 능력의 정도)가 높은 computer를 만드는 것이다. 이를 위해서, 우리는 단순히 하나의 processor를 정교하게 만들기보다는 동등한 기능을 하는 여러 개의 processor를 연결하여 사용하는 것이 더 효율적이라는 것이라는 것을 알아냈다. (이를 software가 잘 활용할 수만 있다면, 성능이 크게 향상될 것이다.)

- 하나의 장치를 동작시키는 방식보다 적은 에너지로 같은 작업을 수행할 수 있다. (동시에 실행시키기 때문에 더 짧은 시간 사용할 수 있다.)
- n개의 processor에서 하나가 실패하여도 n-1개는 정상 작동하기 때문에 전체 시스템은 문제 없이 동작한다. (Redundant, 추가자원을 통해서 가용성을 향상시킴)

이에 따라 우리는 multi-processor를 사용한다.
이는 multi-processor가 어떻게 존재하느냐에 따라서 다음과 같은 형태로 나눈다.

1. **Multicore Microprocessor** : 하나의 IC(집적 회로) 칩에 여러 개의 processor(core)가 존재한다.
2. **Multiple Processor** : IC칩의 갯수를 늘린다.
3. **Cluster System** : Machine(Computer) 자체의 갯수를 늘린다.

따라서, 개인 PC에서는 Multiple Multicore Microprocessor를 지원하고, 있는 상황이고, Datacenter와 같은 환경에서는 이러한 Machine들이 여러 개 존재하는 Cluster System이라고 생각하면 되겠다.

또한, 이용하는 방식에 따라 크게 두 가지로 나눌 수 있다.

1. Task Level Parallelism(=Process Level Parallelism) : 동시에 독립된 여러 program을 실행시키는 방식
2. Parallel Processing Program : 동시에 여러 개의 processor를 이용하여 하나의 program을 실행시키는 방식

## Parallel Processing Program의 구현

하나의 작업을 더 빠르게 처리하기 위하여 multiple processor를 사용하는 software를 작성하는 것은 어렵다. 이는 processor의 수가 늘어날 수록 심해진다. multiprocessor program을 이용할 경우에, 수가 늘어날 수록 우리는 다음과 같은 작업에 대한 부담을 가질 수 밖에 없다.

1. **Scheduling** : process 또는 thread를 scheduling하여 어떤 것을 먼저 실행시킬지에 대한 scheduling 역시 큰 부담이다.
2. **Partitioning** : Memory의 구간을 각 processor에게 어떻게 나누고 서로 독립되게 존재하기 위한 관리를 수행하는 것 역시 큰 부담이 된다.
3. **Balancing the Load** : 작업을 각 processor에게 균등히 분배하는 것 역시 어렵다.
4. **Time to Synchronize** : 여러 개가 동시에 하나의 process를 실행시키면, 읽고 쓰기에서 충돌이 발생하는 것에 의한 문제가 발생하고 이를 해결하기 위해서 시간을 사용할 수 밖에 없다.
5. **Overhead for Communication** : 각 processor간의 의사소통에 너무 큰 비용이 발생하는 경우 오히려 하나의 processor가 실행시키는 것보다 더 많은 시간을 요구할 수도 있다.

이 모든 것을 software에서 제대로 관리할 수 있을 때, 그제서야 우리는 multi processor 시스템을 제대로 활용할 수 있는 것이다.

우리가 processor의 갯수를 늘림으로써 얻을 수 있는 혜택은 각 processor에 전달되는 작업의 수를 균등하게 나누어, 기존에 하나의 processor가 할 수 없던 일을 처리(weak scaling)하거나, 기존의 문제를 더 빠르게 처리(strong scaling)할 수 있다.

## Data Stream, Instruction Stream

processor들로 들어오는 data의 양을 의미하는 **Data Stream**과 instruction의 양을 의미하는 **Instruction Stream**에 따라서, 우리는 각 processor들을 다양한 이름으로 부른다.

1. **SISD**(Single Instruction Stream, Single Data Stream) : 대게 single processor일 경우 이와 같은 형태를 채택한다.
2. **MIMD**(Multiple Instrunction Stream, Multiple Data Stream) : Multiple Processor System에서는 당연히 이와 같은 시스템을 채택한다.
3. **MISD**(Multiple Instrunction Stream, Single Data Stream) : 잘 사용하지 않는 형태이다. 대게는 Data의 처리가 더 많이 발생하기 때문이다.
4. **SIMD**(Single Instruction Stream, Multiple Data Stream) : 하나의 Instruction을 이용하여 복합적인 여러 개의 데이터를 한 번에 처리하는 vector 연산 등을 빠르게 처리할 수 있다.
   1. vector 연산 하나가 for loop 하나를 의미할 수 있다. 이는 processor part의 각 pipeline 단계에서 fetch와 decode에 의한 비용을 크게 감소시킬 수 있다.
   2. 하나의 vector 연산은 내부에서 각각이 독립적으로 수행되기 때문에, data hazard를 check하는 비용이 발생하지 않는다. 👉 따라서, vector의 각 요소를 모두 검사하는 것이 아닌 vector 외부 간의 data hazard 유무만 확인하면 된다.
   3. Main Memory에서 데이터를 불러올 경우에도 각 요소를 불러오는 것이 아닌 한 번에 가져올 수 있기 때문에 매우 빠르다.
   4. Loop를 표현이 vector 연산으로 대체되기 때문에, Loop Branch가 줄어든다.

## Hardware Multithreading

programmer의 입장에서 MIMD는 hardware multithreading처럼 동작한다고 생각하게 한다. 이는 processor의 사용성을 최대화하기 위해서, 특정 thread가 stall 되었을 때, 다른 thread를 수행하도록 하는 방식이다. 즉, 하나의 processor에서 여러 개의 thread를 실행시킨다는 것이다. 그러기 위해 사실상 여러 processor가 존재하는 multiprocessor 환경에서 서로간 실행 환경을 서로 공유해야 한다. 이를 실현하려면, 각 thread의 독립된 상태를 복사할 수 있어야 한다. 즉, 각 각의 register file과 PC가 존재해야 한다. 이들 간의 Memory 공유 같은 경우는 이전에 보았던 Virtual Memory 정보를 공유하여 수행하게 된다. 그리고 무엇보다 중요한 것은 이 실행하는 thread를 바꾸는 시간적 비용이 작아야 한다. 이를 위해서, process가 아닌 thread를 바꾸는 것이다. process를 바꾸는 것보다는 비용이 훨씬 적기 때문이다.

thread를 변경 시에 어떤 방법을 택할 것인가 역시 중요한데, 아래와 같은 방법론이 존재한다.

> **1. Fine Grained Multithreading**

thread의 명령어를 round robine 방식을 이용하여 매번 바꾸면서 실행시키는 방식이다. 변경한 thread 역시 stall이 된 thread라면, 건너뛰고 다음 thread를 실행시킨다.

- 장점 : stall 기간이 짧던 길던 이로 인한 손실을 감추고, 그 동안 다른 thread를 실행시킬 수 있다.
- 단점 : 실행 준비가 된 상태(stall이 아닌 상태)에서도 다음 차례가 올 때까지 반드시 기다려야 하기 때문에 하나의 thread에 대한 처리 속도가 dramatic하게 줄어든다.

> **2. Coarse Grained Multithreading**

하나의 thread에 대한 Instruction만 처리하다가 stall이 발생했을 때에만 thread를 변경하도록 하는 방식이다.

- 장점 : 하나의 thread에 대한 처리 속도의 손실이 적고, switching을 빨리 하는 것에 대한 부담이 적다.
- 단점 : 하나의 thread에 대한 Instruction만 처리하기 때문에, thread를 변경하는 것에 대한 비용이 크다. (long pipeline setup time) 따라서, 짧은 기간의 stall인 경우에는 해당 stall이 끝나길 기다린다.

> **3. Simultaneous Multithreading(SMT)**

Thread Level에서 Parallelism과 Instruction Level에서의 Parallelism을 동시에 수행하는 방식이다. Multiple Instruction 시스템에서는 더 많은 functional unit(register, pc, etc)이 있기 때문에 이를 Multi Threading에서도 적절히 사용할 수 있다는 접근법에서 나왔다. 여기서는 register renaming과 dynamic scheduling을 이용하여 multiple thread에서 여러 개의 Instruction을 빈틈없이 배치할 수 있다. 의존성은 dynamic scheduling이 해결하고, register renaming을 통해 필요에 따라 여분의 register를 불러와서 사용하는 것이 가능해졌다. 이를 통해서 위의 두 방식으로 할 수 없었던, multi processor를 최대한으로 사용하는 효과를 볼 수 있다.

![multi-threading](/images/multi-threading.png)

## GPU(Graphic Processing Unit)

game 산업 및 그래픽 분야의 큰 성장에 힘업어 graphic 처리에 대한 processor의 성능 향상이 필요했다. 즉, 기존 micro processor와 겉아 다용도로 사용되는 것이 아닌 graphic 연산만을 빠르게 처리할 수 있는 processor를 분리할 필요가 생긴 것이다. 이것만을 위해서 만들어진 것이 GPU이다.

GPU는 앞 서 설명한 Multi Threading 기술을 적극 도입했기 때문에 Memory 접근에 따른 Latency가 성능에 큰 영향을 미치지 않는다. 그런 만큼 반대로 높은 Bandwidth를 가진 저장 장치를 필요로 한다.

후에는 이 장치가 수행하는 vector 연산이 여러 용도로 사용됨에 따라 이를 위한 programming language들도 만들어졌다. 대표적인 것이 NVidia가 C를 통해서 만든 CUDA이다.

## Reference

- David A. Patterson, John L. Hennessy, Computer Organization and Design


6. Parallel Processors

5. Memory Hierarchy


해당 내용은 이전에 다루었던, [논리회로 리뷰 내용](/posts/digital-logic-circuit)을 보고 보는 것을 추천합니다.

## Intro

우리의 컴퓨터 시스템은 결국 Finite State Machine(유한상태장치)라고 할 수 있다. 즉, 순서에 따라 유한한 상태에서 다음 상태로 넘어가면서, Output을 계속해서 내보내는 장치라는 것이다. 이때 하나의 작업은 하나의 Clock 단위로 수행되며, 연속적은 작업 처리를 통해서 컴퓨터는 사용자가 요구한 명령을 수행하게 된다.

## Processor

processor와 program의 성능을 측정하기 위해서 우리는 다음과 같은 식을 활용하였다.

$$\text{instruction count} \times \text{Clock Cycle Time} \times \text{Clock Cycles per Instruction}$$

[2. post](/posts/architecture-instruction)에서는 Instruction Count를 관리하고, 어떻게 계산되는지를 보았다면, **해당 포스팅에서는 Clock Cycle Time과 Clock Cycle per Instruction이 어떻게 구성되는지를 알아보며, 이들을 어떻게 줄일 수 있는지를 알아볼 것이다.**

이를 위해서 우리는

1. MIPS CPU의 가장 기본적인 구현
2. pipeline된 MIPS
3. Instruction 단계에서의 병렬화

를 살펴볼 것이다.

```plaintext
 🤔 주의

 해당 단계에서는 다음과 같은 사항은 배제한다.
 1. multiply, shift, divide 연산
 2. floating point 연산

 결론적으로, 앞으로 구현할 MIPS에서는 다음과 같은 연산을 할 수 있다.
 1. Memory에 접근하는 Load Word, Store Word
 2. 기본 연산자 ADD, SUB, AND, OR, 등
 3. Branch 구문 (BEQ, JUMP)
```

## 1. 기본적인 MIPS 구현(Single Cycle CPU)

기본적인 processor에서 program이 동작은 다음과 같다.

1. PC(Program Counter)를 Memory에 보내서 code를 포함한 부분을 특정하여 Instruction을 불러온다.(Instruction Fetch)
2. 하나 또는 두 개의 register를 읽어서 Instruction을 수행한다.

따라서, 이를 수행할 수 있는 논리 구조를 간략히 그려보면, 다음과 같은 형태를 가지게 됩니다.

![Basic MIPS](/images/basic-mips.png)

먼저, PC값의 형성 부분부터 보면 기본적으로 PC는 현재값에 4를 더하는 연산이기 때문에 상단에서 더한 값이 바로 다음 Clock에 적용된다고 할 수 있다. 그런데, 만약 Jump나 Branch 연산이 들어온다면, 해당 PC값에 특정값을 더한 결과로 이동하게 될 수 도 있다.

그리고, 나머지 부분은 PC를 통해서 첫번째 박스에서 Instruction을 골라내고, Instruction의 특정 부분에서 OP와 register 등에 대한 정보를 토대로 Register와 상수 등을 이용하여 ALU 장치에서 OP 정보에 따라 연산을 수행한 뒤에 결과값을 특정 Register에 돌려주거나 Memory에 저장하도록 한다.

물론 위에서는 **mux**(Multiplexor)에서 사용하는 데이터에 대한 내용은 빠져있지만, 아래 그림을 보면 더 정확하게 이해할 수 있을 것이다. 여러가지 경우의 수 중 상황의 따라서 output이 다른 경우에 mux를 사용하게 되는데, 여기서는 Instruction의 특정부분을 통해서 Control bits를 얻어내고, mux를 설치하여 적절하게 행동하도록 제어하고 있다.

대표적인 예시로 아까 PC값을 선택하는 부분이 보다 명확하게 표시되는 것을 볼 수 있다. 현재 계산된 PC+4를 사용할 것인지 아니면, Branch 명령어에서 계산된 값을 사용할 것인지를 Control bit가 결정하는 것을 볼 수 있다.

![Basic MIPS 2](/images/basic-mips2.png)

이제부터는 각 단계별로 뜯어서 살펴본다.

### 1) IF 단계 - Instruction Fetch

해당 단계에서는 PC에 저장된 값에 따라서, Memory에서 Instruction을 추출하면서 PC에 4가 더해지는 것을 볼 수 있다. 그리고, Instruction의 특정 부분과 연산이 수행되는 것을 볼 수 있는데 이는 Branch 구문에 의한 이동을 위해서 주소를 저장해놓는 것이다.

그리고, 이를 mux와 signal bit를 통해서, 최종적으로 다음 Program의 line을 가르킬 수 있다.

![MIPS IF](/images/mips-if.png)

### 2) ID 단계 - Instruction Decode and Register File Read

해당 단계에서는 크게 두가지의 일을 한다.

첫 번째는, Instruction에 포함된 정보를 기반으로 하여 Register를 선택하고, 해당 Register에 해당하는 정보를 내보내는 것이며,

![MIPS ID](/images/mips-id1.png)

두 번째는, Control bits를 생성하는 역할이다.

![MIPS ID](/images/mips-id2.png)

### 3) EX 단계 - Execution or Address Calculating

다음 단계에서는 `R-Type`, `I-Type`에 따라서 두번째(2nd) Register를 사용할지 아니면, 상수로 받아들일지를 선택해야 한다. 이는 이전 단계(ID)에서 생성했던 Control bit를 mux에 통과시키는 식으로 구현한다.

이후에는 control bit들을 통해서 연산의 종류를 선택한 후에, ALU 내부에서 연산을 수행하여 결과값을 내보낸다.

결과값은 일반적인 결과를 내보내며, 추가적으로 beq 또는 여타 연산의 결과를 쉽게 알리기 위해서 zero라는 output으로 결과값이 0인지를 알려준다. 이는 다른 beq와 같은 연산에서 control bit로 사용한다.

![MIPS EX](/images/mips-ex.png)

### 4) MEM 단계 - Data Memory Access

Data Memory에 접근하는 동작으로 만약 Memory에 데이터를 update하는 동작을 한다면, MemWrite가 1로 설정되어있고, 이를 보고 명령어를 처리하게 된다.(read도 동일하게 MemRead를 활용한다.) 물리적으로 CPU와 떨어져있는 장비이기 때문에 접근하는데 많은 시간이 소요된다. 따라서, MIPS의 Instruction 실행의 모든 단계들 중에서 가장 오랜 시간이 필요한 연산이라고 할 수 있다.

![MIPS MEM](/images/mips-mem.png)

### 5) WB 단계 - Write Back

실제로 Register의 값을 update해주는 부분으로 register의 update는 Data Memory에서 값을 불러오거나 연산 결과를 받을 때 사용하기 때문에 둘 중에 어떤 경우인지를 확인하여 데이터를 update한다.

![MIPS WB](/images/mips-wb.png)

위와 같이 하나의 Instruction을 수행하기 위한 일련의 작업이 한 Clock을 단위로 실행되는 경우를 Single Cycle CPU라고 한다.

### 2. Pipelining

가장 기본적인 구조를 살펴보았으니 위의 형태를 최적화하기 위한 가장 효과적이였고, 모든 CPU에서 사용되고 있는 설계 방법을 설명할 것이다. 위의 과정을 보고 있으면 우리는 비효율을 하나 발견하게 된다. **바로 특정 단계가 실행 중인 동안에 해당 단계에 포함되지 않은 장비들은 놀려지고 있다는 점이다.** 즉, 위에서 processor의 성능을 측정하는 지표인 Clock Cycle Time이 증가한다. 따라서, 모든 장비를 계속해서 실행시키기 위해서, 한 단계가 한 Clock이 되도록 하는 방법이 고안되었다.(Multi Cycle CPU)

하나의 예를 살펴보자.

세차장에 갔다고 하자. 우리는 당연히 일열로 서서 자신의 차례가 되기를 기다린다. 하나의 장비가 세차에 들어가기 전에 사람에 의해서 먼저 비누거품을 내는 단계가 있다면, 우리는 당연히 줄을 서있는 동안 세차장 아르바이트생이 비누칠을 해주기를 기다릴 것이다. 하지만, 해당 세차장에서는 만약 기다리는 동안 해주는 것이 아니라 세차 기계가 이전 차량에 대한 작업을 마치고 안정적으로 작업이 끝난 후에 비누칠을 해준다고 하자. 이것은 굉장한 짜증을 유발하는 요소가 될 것이다.

따라서, Single Cycle CPU를 사용하는 것은 하드웨어 장비를 최적화하지 못한 사례라고 할 수 있다.

위와 같이 단게를 나누어 여러 Cycle에 나누어 하나의 명령어를 처리하게 되면, 우리는 다음과 같은 효과를 얻게 된다.

1. Clock Cycle Time이 줄어든다.
2. 하나의 CPU가 동시에 여러 개의 명령어를 실행하게 할 수도 있다.(**Instruction Overlapping**)

![Pipeline Example](/images/pipeline-example.png)

이렇게 Instruction을 동시에(병렬적으로) 실행할 수 있다면, 1개의 Cycle 동안 Hardware 장치의 잉여 시간을 최소화할 수 있다.

하지만, tradeoff 역시 존재한다.

1. 각 단계의 연산이 끝난 후에 해당 값을 보관할 추가적인 하드웨어 장비(register)가 필요하다.
2. Clock이 올라가고, 떨어지는 동안의 미세한 시간의 추가로 시간 비용이 증가한다.
3. Clock Cycle Time은 반드시 하나의 상수로 정해져야 하기 때문에 가장 실행 시간이 긴 단계에 의존하게 된다. 즉, 실행시간이 더 짧은 단계라고 할지라도 다른 긴 단계가 있다면 기다려야 한다.
4. 2와 3번을 이유로 결론상 하나의 Instruction을 수행하는데 걸리는 시간은 증가할 수 밖에 없다.
   그렇기에 결론상 단계를 생각없이 무조건 잘게 자른다고 좋은 것이 아니다. 바로 균등하게 많이 나눌 수 있는 만큼 나누는 것이 좋은 것이다.
5. Instruction을 동시에 실행하는 것으로 인한 문제가 발생할 수 있다(Hazard). 이는 바로 다음 부분에서 다룬다.

### Hazard

Harzard는 아래와 같이 총 3가지의 종류가 있다.

> **1. Structural Hazard**

Hardware가 구조적으로 동시에 특정 Instruction 조합을 처리하지 못할 경우를 의미한다. 즉, 서로 다른 pipeline stage에서 동일한 resource(Hardware)에 접근하고자 할 때 발생할 수 있다. 만약 Instruction Memory와 Data Memory의 분리가 되어 있지 않은 경우에는 이러한 문제가 IF, MEM 단계에서 발생할 수도 있지만, MIPS에서는 발생하지 않는다.

> **2. Data Hazard**

바로 Instruction이 서로 연관(의존)되어있을 때의 문제이다.

다음과 같은 상황을 가정해보자. 우리가 memory에서 데이터를 불러와서 3을 더하는 연산을 한다고 하자. 그렇다면 명령어는 다음과 같다.

```assembly
lw $v 0
addi $v 3
```

이를 실행하면 불행하게도 load가 채 끝나기도 전에 채워지지 않은 \$v에 3이 더해지는 것을 알 수 있다.

이를 해결하기 위해서 3가지의 선택지가 있다.

1. 의존성이 있는 명령어가 실행 중인 경우 끝날 때까지 대기 (**Stall**)
   가장 간단한 방법이지만, pipelining을 통한 성능 향상을 감소시킬 수 있다.
2. Compiler 단에서 의존이 발생하는 Instruction 사이에 순서가 상관없는 Instruction을 끼워넣어서 resource가 낭비되지 않으면서 hazard가 발생하지 않도록 한다. (**Reordering**)
   Hazard를 해결하는 좋은 방법이지만, 항상 이것이 가능할 수는 없다.
3. 추가적인 Hardware를 사용하여 결과값을 필요로 하는 resource에게는 단계를 생략하고 넘긴다. (**Forwarding**, **Bypassing**)
   현재까지는 가장 괜찮다고 받아들여지는 방법이다. 예를 들어서, EX 단계에서 ALU 연산이 끝나자마자 Write Back을 자체적으로 수행해주면 총 3번의 stall을 1번으로 줄일 수 있다.

> **3. Control Hazard**

Branch Hazard라고도 불리며, 이전 Instruction의 결과에 따라서 실행시킬 Instruction이 변화할 때, 어느 Instruction을 실행시킬지 알 수 없기 때문에 발생하는 Hazard이다. (JUMP, BEQ)

이 경우에도 총 3가지의 선택지를 가진다.

1. 성공적으로 분기문이 실행될 때까지 대기한다.(**Stall**)
2. 어느 곳으로 Branch가 될지를 예상하여, 미리 시행해둔다. (**Branch Prediction**)
   Resource를 최적화한다. 별도의 hardware를 설치하여 미리 JUMP 및 Branch address를 계산해 놓는다(**Hardware Optimization**)는 가정이 필요하다. 또한, 예측이 얼마나 적중하는가 역시 굉장히 중요한 요소로 작용한다.
   대게 이러한 예측은 두 가지의 종류가 있다.
   1. 정적 예측
      쉽게 생각할 수 있는 것은 반드시 실패한다고 생각하거나 성공한다고 생각해서 진행하는 방식이다. 좀 더 복잡한 방식은 loop문에 의한 branch인 경우 branch가 수행될 확률이 높다는 것을 기반으로 하여 성공 가능성이 크다고 예측할 수 있다.
   2. 동적 예측
      이전 예측들을 기반으로 하여 현재 예측을 수행하는 방식이다. 이를 사용하면, 여러 번 반복되는 행위에 대한 예측율이 상당히 높아진다. 대게, 우리가 하는 분기문이 loop 등에 의한 경우가 많으므로 좋다고 할 수 있다. 또한, 최근에는 machine learning을 활용하여 예측을 수행하는 방식 또한 나오고 있다.
3. Branch 여부에 상관없는 요청을 Control Hazard에 의해서 발생하는 구간에 넣는다. (**Delayed Decision**)

## Parallelism via Instruction

Pipelining을 통해서, Instruction을 동시에 여러 개 실행시킬 수 있는 환경이 구축되었다. 그 와중에 resourece 자체를 하나 이상 두어서 Instruction을 동시에 수행할 수 있도록 하는 방식이 고안되었는데, 이를 Multiple Issue processor라고 한다.

이를 대표하는 방식은 크게 두가지로 나눌 수 있다.

### 1. Static Multiple Issue

이는 compiler가 program을 기계어로 번역하는 과정에서 이루어지며, 대표적으로 다음과 같은 것들이 있다.

1. VLIW(Very Long Instruction Word)
   의존성이 없는 여러 Instruction을 하나의 Instruction으로 뭉쳐서 실행시키는 방법이다. 이를 통해서 중첩되는 OPCODE 및 기타 처리 등을 최소화할 수 있다. Processor가 해당 기능을 지원하는 경우에만 사용가능하다.
2. Loop Unrolling
   loop를 풀어서 여러 개의 Instruction으로 만들어서 branch로 인한 비용을 줄일 수 있다.

### 2. Dynamic Multiple Issue

processor에서 직접 Instruction이 실행되는 동안 이루어진다. 이는 여러 개의 pipeline을 CPU에 두어 이를 SuperScalar 방식이라고도 한다. 이를 효율적으로 수행하기 위해서는 앞 서 보았던 Compiler 단에서의 조율도 필요하며, 실행 중에 Instruction을 어떻게 나눌 것인가에 대한 Dynamic Scheduling 역시 매우 중요하다. 대표적인 예시가 OoO(Out of Order) Execution을 이용하는 것이다. Instruction의 Fetch를 순서대로가 아닌 의존성에 알맞게 실행되도록 조절하는 방식이다.

## Reference

- David A. Patterson, John L. Hennessy, Computer Organization and Design


4. Processing


## Intro

해당 내용은 컴퓨터 구조를 더 잘 이해하기 위해서 논리회로의 내용을 축약하여 정리한 포스팅이다.

컴퓨터 회로에서는 모든 연산이 이진수로 이루어진다. 그 이유는 높은 전압이 흐를 때를 1, 그렇지 않을 때를 0으로 정의를 하여 이를 통해서 값을 구분하기 때문이며, 이것이 우리가 이진수 체계에서 컴퓨터 연산을 표현하는 이유이다.

만약, 이를 삼진수 이상으로 표현할 수 있다면, 더 획기전 연산이 가능하겠지만, 비용적인 측면과 물리적인 측면에서 아직은 한계가 있다. (양자 컴퓨터 역시 이와 유사한 원리이다.)

해당 분야에서는 0->1로 바뀌는 것을 active(활성화)시켰다고 한다.
또한, 0인 상태를 deasserted signal, 1인 상태를 asserted signal이라고 한다.

---

### Truth Table(진리표)

이진수로 표현되는 값의 input과 이를 통한 output을 나타내기 위해서 우리는 진리표를 활요한다. 여기서는 A,B가 input, C가 output이 된다. C는 A와 B를 OR 연산한 결과이다.

| A    | B    | C    |
| :--- | :--- | :--- |
| 0    | 0    | 0    |
| 0    | 1    | 1    |
| 1    | 0    | 1    |
| 1    | 1    | 1    |

---

### Gate

그림은 위에서 부터 AND, OR, NOR, NAND, 그리고 input을 뒤집는 inversion Gate를 나타낸 것이다.

![AND Gate](/images/and.png)

![OR Gate](/images/or.png)

![NOR Gate](/images/nor.png)

![NAND Gate](/images/nand.png)

![Inversion Gate](/images/inversion.png)

각 Gate는 다음과 같은 연산을 출력한다.

**1. AND**
   2 inputs / 1 output
   | A    | B    | C    |
   | :--- | :--- | :--- |
   | 0    | 0    | 0    |
   | 0    | 1    | 0    |
   | 1    | 0    | 0    |
   | 1    | 1    | 1    |

$0 \cdot0 = 0 \\
0 \cdot1 = 0 \\
1 \cdot0 = 0 \\
1 \cdot1 = 1$

**2. OR**
   2 inputs / 1 output
   | A    | B    | C    |
   | :--- | :--- | :--- |
   | 0    | 0    | 0    |
   | 0    | 1    | 1    |
   | 1    | 0    | 1    |
   | 1    | 1    | 1    |

$0 + 0 = 0 \\
0 + 1 = 1 \\
1 + 0 = 1 \\
1 + 1 = 1$

**3. NOR**
   2 inputs / 1 output
   | A    | B    | C    |
   | :--- | :--- | :--- |
   | 0    | 0    | 1    |
   | 0    | 1    | 0    |
   | 1    | 0    | 0    |
   | 1    | 1    | 0    |

$\overline{(0 + 0)} = 1 \\
\overline{(0 + 1)} = 0 \\
\overline{(1 + 0)} = 0 \\
\overline{(1 + 1)} = 0$

**4. NAND**
   2 inputs / 1 output
   | A    | B    | C    |
   | :--- | :--- | :--- |
   | 0    | 0    | 1    |
   | 0    | 1    | 1    |
   | 1    | 0    | 1    |
   | 1    | 1    | 0    |

$\overline{(0 \cdot0)} = 1 \\
\overline{(0 \cdot1)} = 1 \\
\overline{(1 \cdot0)} = 1 \\
\overline{(1 \cdot1)} = 0$

**5. Inversion(=NOT)**
   1 inputs / 1 output
   | A    | C    |
   | :--- | :--- |
   | 0    | 1    |
   | 1    | 0    |

$\overline{1} = 0 \\
\overline{0} = 1$

여기서 하나 특별한 개념이 나온다. 바로 Functional Complete이다. 특정 Gate만 가지고, 위에서 제시된 모든 연산을 표현할 수 있으면, 이를 Functional Complete라고 한다. 여기서 우리는 가장 보편적으로 생각할 수 있는 {AND, OR, NOT}는 모두 표현할 수 있다는 것을 알 수 있다. 그런데, 여기서 {NAND} 하나만 가지고 이를 표현할 수 있는데, 아래가 이에 대한 예시이다.

![NAND complete](/images/complete-1.png)

그리고, {NOR}만 가지고도 똑같이 표현가능하다.

![NOR complete](/images/complete-2.png)

동일한 값을 NAND, NOR하면 역수가 나온다는 특징과 [드 모르간의 법칙](https://ko.wikipedia.org/wiki/%EB%93%9C_%EB%AA%A8%EB%A5%B4%EA%B0%84%EC%9D%98_%EB%B2%95%EC%B9%99)에 의해서 이것이 정의된다고 할 수 있다.

---

### Decoder

n bit로 표현할 수 있는 $2^{n}$개의 값을 회선을 통해서 표현하기 위해서 $2^{n}$개의 회선 중에서 단 하나의 값만 active한다.

| input1 | input2 | input3 |
| :----: | :----: | :----: |
|   0    |   0    |   0    |
|   0    |   0    |   1    |
|   0    |   1    |   0    |
|   0    |   1    |   1    |
|   1    |   0    |   0    |
|   1    |   0    |   1    |
|   1    |   1    |   0    |
|   1    |   1    |   1    |

| output1 | output2 | output3 | output4 | output5 | output6 | output7 | output8 |
| :------ | :------ | :------ | :------ | :------ | :------ | :------ | :------ |
| 1       | 0       | 0       | 0       | 0       | 0       | 0       | 0       |
| 0       | 1       | 0       | 0       | 0       | 0       | 0       | 0       |
| 0       | 0       | 1       | 0       | 0       | 0       | 0       | 0       |
| 0       | 0       | 0       | 1       | 0       | 0       | 0       | 0       |
| 0       | 0       | 0       | 0       | 1       | 0       | 0       | 0       |
| 0       | 0       | 0       | 0       | 0       | 1       | 0       | 0       |
| 0       | 0       | 0       | 0       | 0       | 0       | 1       | 0       |
| 0       | 0       | 0       | 0       | 0       | 0       | 0       | 1       |

![Decoder](/images/decoder.png)

---

### Multiplexor(=Selector)

Control에 의해서 선택되어진 Input을 Output으로 내보낸다. 이를 위해서 Input 여러 개와 이 중에 무엇을 선택할지를 의미하는 Selector(=Control) Value을 입력한다.
형태는 input의 갯수만큼의 AND Gate와 Output Gate, 그리고 Decoder로 이루어진다.

1. Decoder를 통해서 Signal Bit를 나눈다.
2. 각 Input의 크기만큼 Decoder의 각 Input의 크기를 확장하여 AND 연산을 취한다.
3. 나온 모든 결과를 OR로 연산한다.

| Input1 | Input2 | Signal | Output |
| :----- | :----- | :----- | :----- |
| x      | y      | 0      | x      |
| x      | y      | 1      | y      |

![Mux](/images/mux.png)

---

### Clock

Clock이란 고정된 Cycle time을 주기로 하여 발생하는 신호를 의미한다. 여기서 고정된 Cycle Time은 Clock이 높은 시점과 낮은 시점으로 구분할 수 있다. 우리의 모든 연산은 Clock이 감소하거나 증가하는 그 시점에 동작한다. 이를 `Edge Triggered Clocking`이라고 부른다. 따라서, 우리는 정확히 상태값이 변하는 `edge`에서를 active 상태라고 부르는데 이를 오르는 `edge`로 할지 내려가는 `edge`로 할지는 설계자의 몫이다.

하나의 Clock이 의미하는 것은 특정 상태에서 연산이 이루어져서 다음 단계로 넘어간다는 의미이다. 따라서, Clock Period가 짧을 수록, 다음 상태로 빠르게 넘어갈 수 있다. 하지만, 이를 무한정으로 올리는 것은 불가능하며, 열이 너무 증가하여 회로 전체에 악영향을 줄 수도 있다.

![clock](/images/clock-1.png)

![clock](/images/clock-2.png)

---

### Latches

걸쇠를 의미하며, 값을 저장해놓는다는 의미를 가진다. 이를 이용해서 Memory와 같은 저장장치를 만들 때 사용한다. 두 가지 형태가 존재하니 하나씩 알아보자. (물론 자세히 알면 좋겠지만 필자는 이정도 개념이 있다는 정도로만 기억한다.)

> **S-R Latch(Set Reset Latch)**

S와 R이 모두 0이면 값이 변하지 않고, Cross되는 위치에 데이터가 저장되게 된다.
R(Reset)만 1로 하면, 데이터 값이 0으로 초기화된다.
S(Set)만 1로 하면, 데이터 값이 1로 세팅된다.
R과 S를 모두 1로 하면 해당 값은 저장이라는 의미를 갖지 못한다.

| S    | R    | Q    |
| :--- | :--- | :--- |
| 0    | 0    | keep |
| 0    | 1    | 0    |
| 1    | 0    | 1    |
| 1    | 1    | x    |

![sr-latch](/images/sr-latch.png)

> **D Latch**

Clock단위로 데이터를 저장하기 위해서 이와 같은 장치를 이용한다. 하지만, 이는 Clock이 asserted된 상태(1)인 상태에 언제든지 변환된다는 특징을 갖고 있다. Output은 저장되어있는 값과 등일하다.

![d-latch](/images/d-latch.png)

---

## Flip-Flop

Clock단위로 데이터를 저장하기 위해서 이와 같은 장치를 이용한다. 하지만, 이는 Clock이 변화하는 edge에서만 상태가 변한다는 특징을 갖고 있다. Output은 저장되어있는 값과 동일하다. 아래는 대표적인 D Flip-Flop이다.

![flip-flop](/images/flip-flop.png)

---

실제로는 Latch보다 Flip Flop을 이용하는 것이 일반적인데, 왜 그렇게 하는 것일까? 이는 우리가 입력을 받을 때, 이를 처리하기 위한 최소하의 시간이 필요하기 때문이다.

이 최소한의 시간은 다음과 같이 정의된다.

$t_\text{prop} + t_\text{combinational} + t_\text{setup} + t_\text{skew}$

1. $t_\text{prop}$  : flip-flop 내에서 신호가 처리되는데 까지 걸리는 시간을 의미한다.
2. $t_\text{combinational}$ : 실제 연산이 수행되는 부분이다.
3. $t_\text{setup}$  : 전기적 신호가 바로 low에서 high로 이동하는 것이 아니기 때문에 이를 setup하는데 걸리는 시간을 의미한다.
4. $t_\text{skew}$ : 공정과정에서 완벽하게 만들더라도 각 소자마다 어느정도 차이가 발생하게 되는데 이를 의미한다.

이처럼 이 시간동안 우리는 다른 처리를 수행할 수 없다. 따라서, 이것을 처리하는 동안의 시간을 확보하기 위해서 우리는 Edge에서만 수행하는 방식을 사용하고 있다. 또한, Clock Cycle Time 또한 이보다는 크게 setting하는 것이 일반적이다.


0. 논리회로 요약


## Intro

컴퓨터 구조에서 기본이 되는 **사칙연산**과 **소수**의 표현방식(**Floating Point**)을 다룬다.

## Overflow

시작하기에 앞서서 Overflow라는 개념을 알고가야한다. Overflow란 특정 변수의 표현범위를 벗어나는 경우에 발생하게 되는 에러 상황을 의미한다. 일반적인 사람의 생각에는 수의 범위가 있는 것은 이상할 수 있지만, 컴퓨터에서는 이것이 매우 당연하다. 무한대를 표현하는 것은 사실상 컴퓨터로는 불가능하다. 대신 매우 큰 수를 통해서 표현하는 것이 컴퓨터에게는 일반적이다. 예를 들어 우리가 빈번하게 사용하는 integer 변수 type은 그 값의 범위가 정해져있다. 이는 대게 하나의 변수를 표현하기 위해서 4bytes를 사용하는데 이는 32bits이기 때문에, 최대 $2^{32}$까지가 표현의 범위가 되는 것이다. 여기에 음수를 표현하게 되는 경우에는 범위가 $-2^{31}$ ~ $2^{31}$로 제한된다. 따라서, 이렇게 범위를 벗어나는 경우에 대해서는 programming language 마다 처리가 달라지지만, 대게 에러를 발생시키는 것이 일반적이다. (python에서는 알아서 범위를 추가한다.)

## 덧셈 / 뺄셈

덧셈은 각 자릿수의 합과 이전 자릿수에서 올림된 수(Carry)의 합이라고 다시 해석할 수 있다.
이진수에서는 결국 올림된 수와 두 수가 만들어 낼 수 있는 경우의 수는 00 ~ 11이다.

| A    | B    | Carry | Result |
| :--- | :--- | :---- | :----- |
| 0    | 0    | 0     | 00     |
| 0    | 0    | 1     | 01     |
| 0    | 1    | 0     | 01     |
| 0    | 1    | 1     | 10     |
| 1    | 0    | 0     | 01     |
| 1    | 0    | 1     | 10     |
| 1    | 1    | 0     | 10     |
| 1    | 1    | 1     | 11     |

이를 수행하기 위해서 우리는 XOR 2개와 AND 2개 그리고 OR 1개로 만들 수 있다.(C'와 S가 결과값이다.)

| A    | B    | Carry(C) | A XOR B(D) | A AND B(E) | C AND D(F) | E OR F(C') | C XOR D(S) |
| :--- | :--- | :------- | :--------- | :--------- | :--------- | :--------- | :--------- |
| 0    | 0    | 0        | 0          | 0          | 0          | 0          | 0          |
| 0    | 0    | 1        | 0          | 0          | 0          | 0          | 1          |
| 0    | 1    | 0        | 1          | 0          | 0          | 0          | 1          |
| 0    | 1    | 1        | 1          | 0          | 1          | 1          | 0          |
| 1    | 0    | 0        | 1          | 0          | 0          | 0          | 1          |
| 1    | 0    | 1        | 1          | 0          | 1          | 1          | 0          |
| 1    | 1    | 0        | 0          | 1          | 0          | 1          | 0          |
| 1    | 1    | 1        | 0          | 1          | 0          | 1          | 1          |

![fullAdder](https://upload.wikimedia.org/wikipedia/commons/5/57/Fulladder.gif)

### 음수

음수는 기본적으로 2의 보수라는 방식을 활용한다. 만약 특정 수를 음수로 변환하고 싶다면 전체 수를 반전 시킨 후 `+1`을 수행하는 방식이다. 이를 통해서, 우리는 쉽게 음수를 생성할 수 있다. 그리고 놀랍게도 특정 수를 음수로 변환하고 덧셈을 하게 되면, 이것이 바로 뺄셈이 된다.

## 곱셈

먼저 이진수의 곱셈은 아래와 같이 십진수에서의 곱셈 연산과 방법은 같다.

곱해지는 수(multiplicand), 곱하는 수(multipler), 곱해진 결과(product)이다.

![곱셈 예제](/images/multiplication.png)

하지만, 여기서 하나의 특징을 발견할 수 있다. 각 자릿수의 결과값은 곱하는 수에 의해서 결정된다는 점이다. 곱하는 수가 1이면, 곱해지는 수의 해당 자릿수가 결과값이 되고, 0이면 무조건 0이라는 결과가 나온다는 것을 알 수 있다. 따라서, 다음과 같은 알고리즘에 따라서 연산이 수행된다는 것을 알 수 있다.

![곱셈 알고리즘](/images/multiplication-flow.png)

만약, 음수의 곱셈의 경우에는 간단하게 해당 값을 양수로 변환하고, 연산을 수행한 뒤에 다시 음수로 변환하는 방식을 수행한다.

## 나눗셈

나눗셈은 역시 동일하다.

나누어지는 수(Dividend), 나누는 수(Divisor), 몫(Quotient), 나머지(Remainder) 이다.

![나눗셈 예제](/images/division.png)

이때는 역으로 나누는 수를 오른쪽으로 32번 shift하여 매우 큰 수로 만들고, 나머지를 나누어지는 수로 초기화하여 차근차근 빼보면서 양수이면 빼고, 음수이면 되돌리기를 반복하면서 몫과 나머지를 계산할 수 있다.

![나눗셈 알고리즘](/images/division-flow.png)

## 실수 연산

위에서는 여태까지 정수의 연산을 다루었지만, 소수점을 포함하는 실수 연산을 수행할 때에는 달라지는 사항이 꽤나있다.

먼저, 실수를 표기하기 위한 방법을 먼저 보자.

$$31231.4_{(10)} = 3.12314_{(10)} \times 10^{4_{(10)}}$$

$$100101.1_{(2)}= 1.001011_{(2)} \times 2^{101_{(2)}} $$

이를 일반적으로 normalization이라고 하며, 이진수 체계에서는 다음과 같은 형태를 갖게 된다.

$$\text{1.xxxxx} \times 2^{yyyyy}$$

따라서, 대게 실수를 표현할 때에는 x부분(fraction)과 y부분(exponent) 그리고 부호를 표현(sign)하는 부분으로 나누어서 저장한다. 이 또한, 4byte를 통해서 표현할 경우에는 x부분에 8bits, y부분에 23bits 그리고 부호에 1bit를 할당한다.

따라서, 일반적으로 표현하면 다음과 같이 쓰는 것이 일반적인 실수의 표현이다.

$$(-1)^s \times(1+\text{Fraction})\times2^{(\text{Exponent})}$$

단, 모두 0이면 0으로 친다. floating point 연산은 후에 더 시간이 있으면 자세히 다루겠다.

## Reference

- David A. Patterson, John L. Hennessy, Computer Organization and Design
- Full Adder 이미지는 WIKIPEDIA full adder의 발췌이다. (<https://upload.wikimedia.org/wikipedia/commons/5/57/Fulladder.gif>)


3. Arithmetic

2. Instruction


## Intro

Computer Organization and Design이라는 책을 정리하고 되돌아볼 것이다. 여기서는 가장 기본이 되는 Idea들을 정리할 것이다.

## 1\. 8 Greate Ideas

컴퓨터 구조를 설계하는 과정에서 중요하게 여겨지는 8가지 핵심 아이디어들이다. 뿐만 아니라 이는 전체적인 컴퓨터 과학에서 중요하다고 볼 수 있는 아이디어들이다. 따라서, 앞으로의 Posting에서 Why라는 의문이 든다면, 아래 8가지 이유 중의 하나로 설명할 수 있다.

1. **Moore's Law**  
    18 ~ 24 개월마다 컴퓨터 성능의 지대한 영향을 미치는 IC 칩의 성능이 2배씩 성장한다는 Moore의 주장에서 유래하였다. 즉, **컴퓨터의 성능은 지수적으로 빠르게 성장을 하고 있음을 의미한다.** 이로 인해 구조를 설계하는 과정에서도 현재의 IC 칩의 성능에 맞추는 것이 아닌 이보다 더 큰 성능을 타겟으로 설정을 한다.
2. **Abstraction**  
    우리 말로 추상화라고 표현하며, 복잡한 하위 내용을 모두 기술하지 않고, 간단하게 표현하여 이를 쉽게 사용할 수 있도록 하는 방식이다. 이를 통해서, **설계 과정에서의 복잡도를 줄일 수 있다.**
3. **Common Case Fast**  
    **드물게 일어나는 case보다는 일반적인 case를 빠르게 만듬으로써 성능을 향상시킬 수 있다.** 드물게 일어나는 case는 매우 복잡하고, 해결하기도 난해할 수 있다. 하지만, 대게의 경우 일반적인 case는 간단하다. 이를 최적화하는 것이 전체적인 시스템 성능 향상에 큰 도움이 되는 것은 당연하며 해결도 매우 쉽다.
4. **Performance via Parallelism**  
    성능 향상을 위한 방법은 크게 두 가지이다. 하나는 하나의 장치의 성능을 올리는 것이고 또 하나가 바로 **하나의 작업을 여러 명이 동시에 수행하는 방식이다.**
5. **Performance via Pipelining**  
    성능 향상을 위한 병렬처리 방식 중에서 가장 유명한 방식이 pipelining이다. 쉽게 생각하면, 분업이라고 할 수 있다. **여러 명이서 하나의 목적을 위해 일을 할 때, 효율적으로 작업하기 위해서 업무를 분담하여 동시에 작업**하는 방식이다.
6. **Performance via Prediction**  
    우리는 무슨 작업을 할 때, 아직 결정되지 않은 사항 때문에 기다리는 경우가 있는데, 이것이 어떻게 될지를 **예측하여 기다리지 않고, 미리 진행하자**는 발상에서 나온 것이다. 만약, 이 예측의 적중률이 높다면, 성능 향상에 굉장한 도움을 줄 수 있다.
7. **Hierarchy of Memories**  
    컴퓨터의 사용자가 원하는 메모리는 빠르고, 크고, 싸야 한다. 하지만, 빠르기 위해서는 비싸야하고, 크기 위해서도 비싸야 한다. 그래서 생각해낸 방법이 계층화이다. **빠르고, 작은 memory를 위로 쌓고, 느리고, 큰 memory를 아래로 쌓음으로써 비용을 절감**하자는 것이다.
8. **Dependability via Redundancy**  
    컴퓨터는 빠르기만 해서 되는 것은 아니다. **신뢰**할 수 있는 시스템을 구축해야 한다. 실패하지 않는 시스템을 구축하는 것은 매우 힘든 일이기 때문에, 우리는 **여분 장치**를 두어 이를 통해서 실패 시에 이를 떠맡을 수 있도록 하는 설계를 해야 한다.

## 2\. Below Your Program

program 밑에는 무엇이 있는가?

우리의 program은 모두 application software이고, 이는 hardware 바로 위에 존재하는 것이 아닌 system software위에서 동작하게 된다.

![kernel](/images/kernel.png)

**System Software**는 Hardware를 직접적으로 제어하거나 computer가 작동하기 위해 필수적이며 기본적인 softwre를 말한다. 그 중에서 가장 대표적인 것이 OS이고 **OS**는 사실상 우리가 보는 Software와 Hardware 간의 interface역할을 한다. 예를 들어, memory 관리, process 관리 등(이는 OS 에서 자세히 배웁시다.)을 수행한다. 반면, **Application** **Software**는 직접적으로 hardware를 관리하거나 필수적인 요소는 아니지만 computer를 통해서 가치있는 작업을 수행하도록 한다. 대표적인 예시가 웹브라우저, word, game 등이 여기에 포함된다.

  그렇다면, 우리가 만든 코드(Application Software)가 어떻게 실행되어질 수 있을까? 이 또한, System Software인 compiler, assembler, linker, loader의 도움을 통해서 실행되어진다. **compiler**는 우리가 고 수준의 언어(C++, Java, 등)로 만든 software code를 Assembly 언어로 변경한다. 그러면, 이를 **Assembler**가 0과 1로 이루어진 기계어로 번역해준다. 해당 작업이 끝나면, **Linker**가 나타나 여러 개로 나뉘어져있던 이 파일과 기존 라이브러리를 하나의 파일로 묶어주는 역할을 한다. 이 작업을 마치고 만들어진 최종 파일을 실행하고자할 때, **Loader**는 이를 memory에 올리는 역할을 한다. 이렇게 실행된 program은 여기서 그치지 않고, memory의 아예 다른 영역에 위치하는 library도 불러와서 사용하는 것이 가능하다. 이것을 **Dynamic Linked Library**(DLL)라고 한다.

![run-process](/images/run-process.png)

이렇게 하나의 코드를 작성하면, 실제로 실행되기까지 여러 작업들을 거쳐야만 한다. 그럼에도 assembly 언어나 기계어를 사용하여 코딩을 하지 않는 이유는 아래 세 가지 이유가 주요하다.

1. 사람이 이해하기 쉽다.
2. 생산성을 높일 수 있다.
3. Compiler와 assembly를 통해서 어디서든 돌아가는 프로그램을 제작할 수 있다.

## 3\. Under the Covers

우리의 컴퓨터는 어떻게 이루어지는가를 크고 얇게 한 번 알아볼 것이다.

- **Input Device** : 우리의 입력을 받는 부분이다. 마우스, 키보드, 터치스크린 등이 있다.
- **Output Device** : 우리가 출력을 받는 부분이다. 모니터, 프린터 등이 있다.
- **IC(Integrated Circuits, Chip)** : 집적 회로로 번역되어지며, 통상 우리가 chip이라고 부르는 녀석들이다. 이들은 적게는 수십개 많게는 억 단위 이상에 이르는 양의 transister를 가지고 있고, 이를 통해서 데이터를 저장하거나 처리하는 역할을 할 수 있다. 즉, IC를 통해서 CPU, Memory를 만들 수 있다.
  - trasistor: 쉽게 말해서 전기를 통해서 on/off를 수행할 수 있는 switch라고 볼 수 있다. 이를 통해서, 데이터를 연산하거나 저장하는 것이 가능하다.
- **CPU (Central Processor Unit, Processor, MicroProcessor)** : 중앙 처리 장치라는 의미로, 각종 연산과 I/O Device 처리 등의 중심 역학을 수행한다. CPU는 크게 두 개의 요소로 이루어진다.
  - DataPath : 수학적인 연산을 수행한다.
  - Control : program의 instruction이 무엇을 요구하는지를 입출력 장치, memory 또는 datapath에 전달합니다.
- **Memory(RAM(Random Access Memory), main memory, primary memory)** : 실행되고 있는 프로그램이 위치하는 곳이다. 실행되는 프로그램에 대한 정보와 같은 내용을 포함한다고 할 수 있다. 이는 DRAM으로 이루어진다. 또한, Random Access Memory라고 불리는 이유는 어느 위치에 데이터를 저장하고 있어도 해당 데이터를 찾는데 걸리는 시간이 동일하기 때문이다.
  - DRAM(Dynamic Random Access Memory) : IC chip을 통해서 만들어진다. 여기서 Random Access란 접근할 때, 앞에서부터 차례로 접근하는 것이 아닌 한 번에 바로 짚을 수 있음을 의미한다.
- **Cache Memory** : 대게 Cache라고도 부르며, Processor 내부에 존재하는 memory라고 볼 수 있다. 즉, 실제 Memory의 buffer 기능을 한다. 여기서는 SRAM을 사용한다.

- SRAM(Static Random Aceess Memory) : DRAM보다는 빠르지만, 집적도가 낮고 더 비싸기 때문에 많이 사용할 수는 없는 chip이다. 하지만, 성능 향상을 위해서 processor 바로 앞에 buffer로써 사용한다.
- buffer : 자료구조의 queue를 이용한 것으로, 처리를 요청한 대상과 처리를 수행하는 대상 사이에서 데이터를 잠깐 보관하기 위한 장소로 사용된다.

- **Secondary Memory** : main memory는 휘발성이라는 특징을 갖고 있기 때문에 시스템이 종료되어 전기가 더 이상 공급되지 않으면, 모든 데이터는 날라간다. 이를 막기 위해서 그리고 부족한 main memory의 저장공간을 보조하기 위해서 보조 기억 장치를 사용한다. 이것에 사용되는 것은 크게 두 가지 이다.
  - magnatic disk : 자기 disk를 이용해서 정보를 저장하는 방식이다. 전기가 공급되지 않음에도 정보를 저장하고 있을 수 있다.
  - flash memory : 반도체를 이용하여 데이터를 저장하며, DRAM보다는 느리지만, 더 싸고 휘발성이 없다.
- **Instruction Set Architecture(ISA, architecture)** : 0과 1로 이루어진 기계어가 들어왔을 때, 이것이 무슨 의미인지를 나타내는 instruction Set에 따라 CPU가 알맞은 연산을 수행하는 architecture이다.
  - Instruction Set : hardware에게 동작을 요청하는 하나의 명령어를 Instruction이라고 한다. 이들이 무슨 역할을 하는지를 정리해놓은 것이 Instruction Set이다. 이를 통해서, Operating System은 hardware에 접근하여 특정 동작을 수행시킬 수 있다.
  - ABI(Application Binary Interface) : application 단에 programmer가 hardware 작업 등을 수행하기 위하여 호출할 수 있다. 이를 통해서, binary한 동작도 application programmer가 조작할 수 있다. 일반적인 API와 역할이 동일하지만, programming language가 아닌 machine language를 사용하여 구현되기 때문에 hardware 접근 등에 제한이 없다.

## 4\. Performance

우리가 Computer의 성능을 측정하는 것은 중요하다. 왜냐하면, 이를 지표로 계속해서 computer의 성능을 향상시켜야 하기 때문이다.

그래서 우리는 다음과 같이 표현하는 것이 일반적이다.

$$\text{Excution Time} = \text{Clock Cycle Time} \times {\text{Number of Instruction}} \times {CPI}$$

즉, **총 실행 시간**(Execution Time)은 **한 번 Clock이 회전하는데 걸리는 시간**(Clock Cycle Time)에 해당 **program의 instruction 수**(Number of Instruction) 그리고 **하나의 instruction을 처리하는데 걸리는 clock cycle의 횟수**(CPI)라고 볼 수 있다.

즉, 우리가 특정 프로그램을 빠르게 돌리고 싶다면, 다음과 같은 식으로 생각할 수 있다.

1. 한 번 회전하는데 걸리는 시간을 줄이기 위해 클락 frequency를 높인다. **하지만, 회전열로 인해 현재는 frequency를 올리는 것은 포기하고 있다.**
2. 프로그램을 잘 짜거나 Compiler를 더욱 더 최적화하여 instruction의 수를 줄인다.
3. 하드웨어를 잘 설계해서 명령 하나를 처리하는데 걸리는 시간(CPI)을 줄인다.
4. 동시에 여러 CPU를 실행시켜서, 실행을 하는 unit 자체를 더 만드는 방법도 있다.

따라서, 앞으로 우리가 Performance를 올리기 위해서, Compiler를 어떻게 최적화할지를 개략적으로 배우며, 하드웨어를 어떻게 잘 설계할지를 자세히 알아볼 것이다. 또한, Parallelism을 통해서 작업을 더 빠르게 수행하는 방법 또한 다룰 것이다.

---

## \+ Amdahl's Law

작업의 성능을 개선시켰을 때 이전과 비교하여 얼마나 효율이 증가했는지를 보여주는 지표이다.

$$1\over{(1-P) + {P\over{S}}}$$

여기서 개선된 작업이 전체에서 차지하는 비율을 P라고 하고, 해당 작업의 향상된 작업 효율을 S라고 한다.

만약, 전체에 10%를 차지하는 작업을 2배 빠르게 진행한다면,

$${1\over{(1-0.1) + {0.1\over{2}}}} = {1\over{0.95}} \approx 1.05$$

따라서, 단기간의 성능향상을 하고 싶다면, 비율이 큰 작업의 성능향상을 꾀하는 것이 좋다는 것을 알 수 있다.

## Reference

- David A. Patterson, John L. Hennessy, Computer Organization and Design
