순환식의 형태를 가지고 있기 때문에 어느지점에서 시작해도 무방하나

Instruction address calculation부터 시작한다고 생각하면

최초에 instruction address calculation을 통해서 Instruction을 가져올 주소를 계산한다

흔히 Program counter에 int값을 더하는 방식으로 많이 진행된다

해서 instruction fetch를 통해서 instruction을 Memory에서 가져오고

instruction operation decoding을 통해서 Memory에서 가져온 instruction을 decoding하여

해당 instruction을 수행할수 있도록 한다

그리고는 Operand address calculation과 Operand fetch을 통해서 operand 에 해당하는 것들을 메모리에서 가져온다

예를 들어서 C = A + B라고 한다면 A 와 B에 해당하는 값을 메모리에서 가져온다

그리고는 Data Operation에서 계산이 수행된다

그 다음 Operand address calculation 과 Operation fetch를 통해서

C = A + B를 계산했다면 C의 주소를 계산하여서 A + B를 계산한 결과를 C가 가리키는 주소에 저장한다

그다음은 next instruction으로 넘어간다

CPU는 Central Processing Unit 중앙처리 장치로

CPU vs Core vs Chip

컴퓨터의 구성 단위중 기억, 연산, 제어 3대 기능을 종합하는 장치이다

Core는 각종 연산을 하는 CPU의 요소이다

CPU의 내부에는 Core 말고도 컨트롤러 캐시메모리 등이 있는데

프로그램의 instruction을 읽고 실행하는 역할을 가진다

Chip은 컴퓨터의 actual integrated circuit을 나타낸다

Micro processor vs. Multi processor vs. Multicore processor

multicore는 single cpu에 multiple execution unit이고

multi processor는 2개 이상 복수개의 CPU를 가지고 있다

microprocessor는 computer system의 central unit으로 산술 또는 논리 연산을 수행한다

사진 출처:https://slideplayer.com/slide/5832436/19/images/3/Multi-Core+vs.+Multi-Processor.jpg

Q. add는 4가지 (add, add immediate, add unsigned, add immediate unsigned)가 있는데, subtract는 2가지(subtract, subtract unsigned)만 있는 이유는?

subtract immediate의 경우 add immediate를 사용하여 음수를 주게 되면

같은 역할을 할수 있기 때문이다

Q. HI 레지스터와 LO레지스터 용도는?

일반적 범용레지스터와 달리 multiplication 과 division의 결과를 저장하기 위한 목적으로 사용되는 특별 레지스터이다 instruction mfhi 와 mflo를 통해서만 접근된다

Q. shift right는 logical, arithmetic 연산이 있는데, shift left는 logical 연산만 있는 이유는?

shift right의 경우 빈 공간을 0으로 채우면 되지만

shift left의 경우 음수와 양수에 따라서

부호를 유지하여 sign bit로 확장하는 경우와

부호를 무시하고 shift right와 마찬가지로 0으로 확장하는 경우가 있다

Q. MIPS 프로세서는 메모리에 접근할 수 있는 방법은 load/ store instruction에 의해서만 가능하다. 이유는?

파이프라인 구조를 위하여

메모ㄹ에서 데이터를 레지스터에 가져온 후 다른 명령어가 메모리에 접근하지 않기 위하여

shift right는 부호와 상관없이 같은 결과를 보여내기 때문이다

Q. jump 명령어의 target address가 어떻게 계산되는지.

26bit를 통해서 접근하지만

주소는 32bit 이므로

6bit가 더 필요한데

byte 단위이기 때문에 뒤에 00은 고정된다

그리고 앞에 4bit는 program counter의 앞 4자리를 가져와서 사용된다

한사이클에 안하고 여러 스텝을 두고 여러 스텝을 한사이클에 실행

서로다른 instruction이 서로 다른 cycle 수에 실행된다

• 1.instruction을 memory로부터 읽어온다(instruction fetch)

• 2.instruction이 뭔가를 살펴보고 register 두개를 읽는다(instruction decode/register fetch)

• 3.ALU연산(ALU Operation)

• 4.Register에 가서 target register update

load라면

유사하지만

3.에서 address를 계산하고

4.에서 memory를 읽고

5.register에 target register udpate

만약 4,5를 합쳐서 한번에 하면 cycle time이 커져서 모든것이 피해를 받는다

multicycle에선 resource를 각 사이클마다 다른용도로 사용

memory unit도 instruction memory data memory 따로 있지 않고

single memory로 존재한다

adder또한 마찬가지로 single ALU로 존재

하지만 multi cycle에선 해당 cycle 말고 다음 cycle까지도 필요한 것들을 저장할 temprorary register 등장

그래서 시간이 오래걸리는

• memory access

• register file access

• ALU operation

이것들은 한번에 하나만 할수있다 at most

녹색이 temporary register

ALU memory 통합

1,2에서는 동일한 기능 수행

R type은 후에 2 cycle 수행

action for memory-reference instructions

즉 load or store의 경우 공통적으로 3번째에서 주소를 계산하고

load면 4에서 메모리에서 읽고 5번째에서 target register에 적는다

store라면 3에서 주소를 계산하고 4에서 그 주소에 register 값 하나를 적는다

branch는 추가로 하나만 필요한데

A 와 B가 같은 경우엔 PC의 주소를 target address로 update 해준다

jump도 마찬가지이다

PC에 해당하는 걸 memory에서 가져온다

PC를 4더한다

이걸 그림에서 보게되면

PC값을 메모리에 집어넣고 그럼 instruction이 나온다

그리고 pC에 상수 4를 더해서 PC로 들어간다

그러면 1번째 cycle이 끝나면 instruction 32bit가 memory 뒤에서 기다리고 있는다

첫번쨰 클락의 falling edge가 발생하면 instruction 32bit가 instruction register에 들어오고

PC의 값이 PC + 4가 된다

하지만 branch jump에선 PC + 4가 굳이 필요없지만 한다

이걸 speculation이라고 한다 실행까지 더하면 speculative execution이라고 한다

register 해당 위치에 있는 두 값을 읽어서 temporary register에다가 집어넣는다

그리고 branch target address를 계산한다

R format 3번쨰 cycle에선 두 register 값에 ALU operation을 가한다

4번쨰에선 ALUout값을 target register에다가 적으면 된다

instruction register에서 source register 두개를 읽어서

그 register 값을 A B temporary register에 적어두고

PC +4의 값하고 instruction의 16비트를 sign extend해서 * 4해서 두개 더하면 branch target address가 된다

두번째 사이클이 끌날떄는 레지스터 두개값이 AB 앞에서 기다리고

branch target address 가 ALU 뒤에서 기다린다

falling edge가 되면 AB에 들어가고 branch target address는 ALUout에 들어간다

3번째 cycle부터는 각자 갈길 가는데

R type의 경우 두개 A B를 어떤 r type인지에 따라 operation하면 된다

ALU에서 해당 operation을 계산해서

ALUout에 넣고

마지막 cycle에서는 target address 적힌 값 write data로 보내주고

target register를 instruction으로 부터 읽어서 taget register의 번호로 update한다

4번쨰 cycle이 끝날때에는 write register와 write data 앞에서 기다리고 있는다

클락의 falling edge때 target register의 값이 변한다

A에는 이미 있고 instruction 16 bit을 32bit으로 sign extend 한것을 ALU에서 더해서

ALUout에 저장

3번쨰 cycle의 끝쯤 되면은 ALU 뒤에서 기다리고 있다가 falling edge때 ALUout으로 들어간다

Load의 경우 ALUout에 해당하는 주소에서 메모리에서 읽어서 MDR이라는 또다른 temporary register에 저장

cycle이 끝날때 memory data register 앞에서 기다리고 있다가

falling edge때 들어간다

5번째는 target register에 각각 적는거다

5번째 사이클에 write register write data 앞에서 기다린다

store의 경우

B에 있는 값을 메모리에 쓴다

B의 값을 memory의 writedata로 보내고 주소는 ALUout에서 온다

branch의 경우 이미 branch target address를 계산했기 때문에

두 register의 값이 같다면 ALUout에 해당하는 address로 PC를 이동하고

그렇지 않다면 아까 수행한 PC +4 로 간다

jump의 경우 PC에서 4bit 떼어오고 뒤에 00 붙힌다 그다음 concat해서 PC로 보낸다

다양한 control signal 필요

어떤 cycle에 있는지 파악 필요하다

그 과정에서 필요한게 finite state machine이다

output이 control signal이 될것이다

next state function이 다음의 어떤 state로 갈지 정한다

무어와 밀리가 있지만

우리는 state만 알면 되서 무어이다

해당 state에 따라서 control signal을 다 만들어낼수 있다

state register를 통해서 10개중 어떤 state인지 알고 instruction opcode를 통해서

어떤 instruction인지 파악하여 control signal과

다음 state는 뭔지를 파악할수 있다

PLA의 핵심은 모든 logic function은 sum of product로 이루어진다

exception은 지금 실행되고 있는 instruction이 유발한 exceptional한 event

interrupt는 지금 실행되고 있는 것과는 상관없이 외부에서 asyncronized하게 들어온 exceptional하게 들어온 event

exception이건 interrupt건 operating system에게 control이 간다

나중에 실행되고 있는 프로그램으로 돌아가기 위해

EPC(Exception program counter)에 현재 PC를 저장한다

어떤 이유로 발생하였는가에 대해서 CAUSE라는 register에 저장

그러고 나서 operating system에서 exception 또는 interrupt를 처리하는 곳으로 이동

EPC에 있는 값을 PC로 돌아가서 원래 돌던 user program으로 돌아감

EPC와 CAUSE는 PC와 마찬가지로 Machine state에 포함된다

​ 이유는 operating system이 만지기 위해서다

Mips 1

역사적으로 중요한 의미를 가짐

예전에는 1 Chip 안에 들어가는 Transistor 개수가 exponential하게 증가했지만 아직 프로세서 전체를

1 chip에 구현할 정도는 아님

이 시점에는 이정도 transistor 개수는 single chip processor로 할수 있겠다

cisc에서 risc로 변화하는 시점임

risc architecture의 가장 중요한 요소는

• Pipelined execution
• Cache memory

나머지는 이 두개의 부가적인 느낌임

Mips는 일부 임베디드 에서 아직 사용중임

General Purpose Register 32개

흔히 범용 레지스터라고 부름

0번 레지스터는 항상 0을 지니고 있음

어찌 보면 Read Only Register라고 볼수 있음 아무리 다른 값 넣어도 0을 지니고 있음

예외를 만든 이유는 0을 많이 사용하기 때문이다

R format의 특징

​ Register 3개 지정 각각 5bit

​ shamt :얼마나 shift 하냐

​ 마지막 funct 은 opcode의 확장

​ 즉 opcode space가 더 넓다

I format

​ 16상수와 Register 2개 필요

J format

​ jumpy에만 사용

addi $s1 $s2 100

I format이고 상수는 16bit인데 32bit로 확장할려고 하면

sign bit으로 앞 16개를 쭉 집어 넣어야 한다

signed 연산이기 때문에 overflow 발생 가능성 있다

overflow

​ 양수 + 양수 or 음수 + 음수의 경우 발생 가능

subtract는 2개 밖에 없는 이유

​ subtract immediate는 add immediate를 음수로 주면 된다

16bit 밖에 안되기 때문에 나머지는 0으로 채워버림

shift left logical 왼쪽으로 밀고 0으로 채워버림

0111을 shift left 2 bits하면 1100이 된다

shift right는 두개가 있다

left의 경우 연산으로 생각하면 X 2인데

right shift는 %2이다

right shift logical은 밀고 0을 채워넣고

arithmetic은 0이 아닌 sign bit를 채워 넣는다

ex)

1000을 logical right 1bit하면 0100

arithmetic으로 하면 1100

load upper immediate

​ 사실 load가 아님

​ lui $s1 40이면 처음에 40을 넣고 16 bit를 left shift한다

​ 32 bit중 앞 16bit를 주어진 상수로 채우고 싶다

​ 즉 실질적으로 memory load하는 것은 없다

store word

​ 레지스터 안에있는 32bit를 지정된 주소로 쓰는 거다

​ halfword는 16bit

​ store byte 1 byte 저장

​ store float는 floating point에 있는 4 byte

​ swc1인데 c1의 의미는 coprocessor

​ coprocessor 0은 memory management unit(MMU)

​ 1은 방금 사용한 floating point

load word

​ 주소에서 지정된 4 byte채움

load halfword

​ signed로 하면 양수 음수 취급

​ 채우는걸 sign bit로 하냐 마냐를 정하는 거다

load word는 꽉차서 sign bit 여유가 없다

ex)

lw $s1 21($2)가 있다고 하면

주소가 4의 배수 규칙을 지켰는지 안지켰는지 알고싶다면

$2의 값을 알아야 최종 주소를 알수 있다

즉 여기선 모른다

두가지 방식이 있다

network protocol에서 심각해진다

branch on equal 동일하면 L로 이동

opcode가 6bit이기 때문에 32bit를 지정할수가 없음

26bit만 남음

byte주소로 뒤는 00으로 끝남 그래서 생략

이제 28bit 확보

다음 4bit은 현재 Program counter에서 앞 4bit를 떼옴

즉 PC 4bit + 원래 26bit + 00

jump and link 돌아올 지점을 남겨둠

g와 h는 일시적인 값만 의미있기 때문에 temporary 레지스터 사용

배열은 base 주소와 i 만 저장

base address + 4 * i

$t1에 4i를 담는다

else와 exit은 32bit가 아니지만 컴파일러가 알아서 한다

L0 주소

L1 주소

L2 주소

L3 주소

이런 형식으로 한것을 jump table이라고 한다

실제로 없지만 다음과 같이 입력하게 되면

컴파일러가 알아서 바꿔준다

$s2는 바뀌면 안되고

다음과 같이 바뀌지 말아야 하는것은 안바꾸고

바뀌어야할 값만 건드려야 함

번외

sequential execution에서

exception도 sequantial을 따라야 해서

out of order로 먼저 exception이 발생되었다 해도

그전에 있는 instruction들이 실행되기전까지 exception을 발생시키면 안된다

요약하면 해당 exception전에는 다 실행되어야 하고

뒤에는 전부 실행되지 않았어야 한다

마찬가지로 out of order로 먼저 실행될수도 있지만

레지스터 값을 바꿔야 한다면 바꾸면 안된다

왜냐하면 그전에 있는 instruction이 exception이 날수도 있기 때문이다

address mode

정해진 명령어의 비트들은 그 수에 있어서 매우 제한적이다

큰 메모리를 지정하기 위하여 방법들이 있는데 그게 address mode이다

1. 즉치

   프로그램에서 상수값으로 사용

   ex) Mov R1 #8H

   operand 안에 직접 값을 넣는다

   메로리로부터 데이터를 인출하는 과정이 필요없다

2. 묵시적

   말 안해도 알아서 처리한다 즉 내포되어있다

   Sp 가 유효주소가 된다

   Asl 2 -> AC <- AC << 2

   accumulator가 표시되어있지 않아도 알아서 한다

3. 직접

   opearand가 즉 유효주소가 된다

4. 간접

   직접 주소 지정의 단점인 메모리의 표현 한계인데

   또 다른 주소 정보를 사용해서 더 큰 영역의 메모리 접근을 확보할수 있다

5. 레지스터

   연산에 사용될 데이터가 레지스터에 저장되어있다

   opearand 내용이 레지스터 번호로 사용된다

   즉 메모리 접근할 필요가 없다

6. 레지스터 간접

   operand에서 지정한 레지스터 내용이 메모리 주소 정보이다

7. 변위

   offset 사용

   레지스터와 변위를 사용하여

   유효주소는 레지스터 내용에 변위를 합하여 계산된 결과이다

프로그램을 실행하던중 하드웨어적 또는 소프트웨어적 요소로 인해서 exception이 발생 할 수 있다

그렇다면 이 exception이 어떤 원인에 의해서 발생했고 어디서 발생했는지 저장을 하기 위한 레지스터가 필요한데

이때 사용되는 레지스터가 Cause와 EPC(Eexception Program Counter)이다

Cause같은 경우 아까 말한 전자에 해당되서 어떠한 원인에 의해서 exception이 발생되었는지 저장하는 것이 목적이다

반면 EPC같은 경우 PC 어디에서 exception이 발생되었는지 저장하는 것이 목적이다

Cause에 원인을 저장하게 되면 나중에 그 값을 읽어야 할때가 오는데

그때 사용되는 명령어가 move from coprocessor 0 즉 mfc0다

예를 들어서 $t0에 Cause의 값을 옮긴다고 가정하게 되면

mfc0 $t0, Cause

위처럼 사용할수 있는 것이다

mfc0의 opcode는 010000 00000 $t0 Cause 00000000000

처럼 사용할 수 있다

위의 표는 Exception의 종류이다

보다시피 Hardware Interrupt System Call 등 다양한 원인이 존재한다

이 밖에도 다양한 Exception이 존재하지만 대표적인 5가지만 보여주었다

이번 프로그램은 사진의 출간년도, 사진의 제목, 사진감독 3가지 데이터를 general list로 구성하는 것이다

non generic으로 진행하며 multi linked list로 구성한다

먼저 multi linked list를 보게 되면 일반적인 linked list와 차이점은

일반적인 linked list가 하나의 key값을 사용하여 oreder를 한다면

multi linked list는 2개 이상 복수개의 key값을 사용하여 oreder를 하는 특징이 있다

예를 들어 이번 코드처럼 3가지 데이터를 가지고 구성한다면 사진의 출간년도 뿐만 아니라

사진의 제목으로도 정렬을 하는 것이다

물리적인 데이터는 일반적인 single linked list와 동일하지만 HeadNode에서 두개의 key값을 선택하여

연결하는 것이다

필요한 구조체들을 선언한다

사진의 정보를 담고있는 SPICTURE 구조체이다

사진의 출간년도 year

사진의 이름 char형 배열으로 arrTitle

사진 감독 이름 동일하게 char형 배열으로 arrDirector

사진의 정보를 담고있는 SPICTURE 포인터

Key를 year로 했을 경우 다음 노드를 가리키기 위하여 자기 자신의 주소를 담는 포인터 yearNode

Key를 title로 했을 경우 다음 노드를 가리키기 위하여 자기 자신의 주소를 담는 포인터 titleNode

SDataNode의 경우 typedef을 구조체 선언보다 앞에서 진행하는데

이유는 구조체 선언에서 구조체 내부에서 자기 자신의 포인터를 사용하기 때문에

구조체보다 앞에서 미리 선언을 하는 전방선언을 한다

만약 하지 않으면 구조체 선언부에서 SDataNode* 에 대한 정보가 없다고 오류가 뜨게 된다

다음은 SHeadNode인데

현재 요소의 개수를 알려주는 count

Key값을 year로 했을 때 첫번 째 노드를 가리키는 yearFront 마지막 노드를 가리키는 yearRear

Key값을 title로 했을 때 첫번 째 노드를 가리키는 titleFront 마지막 노드를 가리키는 titleRear

마지막 preNode같은 경우는 Search 같은 함수를 실행 할 때 찾고자 하는 target data 뿐만 아니라

직전의 데이터 또한 필요한데 이때 저장을 위한 임시 저장소로 사용된다

구현한 구조체인 SHeadNode SDataNode SPICTURE 인데

SPICTURE 에는 각각 임의의 값을 지정해 두었다

SDataNode 의 요소중 picture이 SPICTURE을 가리키는데 주소값으로 연결하면

그 다음 Key값인 year 와 title에 대해서 정렬 된 순서로 연결을 하여야 하는데

year의 경우 오름차순으로 정렬을 하여 8 -> 9 -> 10 순서가 되어야 한다

SHeadNode의 yearFront는 첫번째 노드인 8을 가지고있는 노드를 가리키고

첫번 째 노드의 yearNode는 9을 가지고 있는 노드를

10을 가지고 있는 노드는 마지막 10을 가지고 있는 노드를 가리키고

10을 가지고 있는 노드는 마지막 노드임으로 NULL을 가리킨다

yearRear는 마지막 노드를 가리킨다

Year에 대해서 연결을 했으니 이번엔 Title에 대해서 연결을 해야한다

Title 또한 Year와 같은 방식으로 알파벳 순서로 가장 앞선 apple 노드를 titleFront가 가리키고

apple 노드의 titleNode는 다음 순서인 bear 노드를

bear노드는 마지막 노드인 cat 노드를 가리킨다

cat 노드는 마지막 노드임으로 NULL을 가리키고 동시에 titleRear도 cat노드를 가리키게 된다