FSM

미국 UC 버클리에서 시작된 언론의 자유 운동. 베트남전 당시 언론과 speech에 대한 통제에 대한 반발로, Mario Savio의 주도로 이루어졌다. 현재 UC 버클리에서는 이 일을 기념하는 까페가 도서관 내에 있다.

컴퓨터 프로그램을 설계할 때 쓰이는 모델이다. 컴퓨터 내에 유한한 상태를 가지는 기계가 있다고 가정하고, 컴퓨터는 오로지 하나의 상태만 갖고 있을 수 있으며 각 상태별 동작과 상태끼리의 전이에 대한 내용을 설계하게 된다.

요컨데, 순서도와 비슷한 것이며, 공대를 가게되면 여러모로 써먹게 된다. Moore FSM과 Mealy FSM이 있으며, 밀리 FSM은 상태(state)와 입력에 따라 순서가 결정되고, 무어 FSM은 상태에만 따라 순서가 결정된다.
대게, 시스템이 복잡해지면 복잡해질 수록 밀리 쪽은 신경 써야할 것도 많아지고 감당하기 어려워지기 때문에 무어 FSM을 사용한다.

MIPS로 만든 멀티 사이클 CPU를 예로 설명한다면, Fetch(명령어 읽기), decode(명령어 해석), execute(명령어 실행), memory access(메모리 접근), writeback(쓰기)이 있는데 각각의 동작 방식은 CPU/구조와 원리문서를 참고하기로 하자.

1. 우선, MIPS로 주어진 명령어가 Fetch로 들어가서 주어진 명령을 가져오면서 동시에 PC+4연산을 하는 상태가 된다.(Fetch)

2. 가져온 명령을 해석 해야하는 상태라 ALU가 할 일이 없으니 혹시모를 branch(분기)명령어에 대비해 레지스터의 [15:0]를 shift-left 2해서 pc와 더해놓는다.(decode)

3-1. 해석 결과 R타입이다. 그렇다면 rs와 rt연산을 한다. 그 후 4-1로 간다.(execute)

3-2. 해석 결과 j명령어다. 그렇다면 명령하는 대로 점프를 하고 1로 돌아가서 다음 명령을 기다린다..(execute)

3-3. 해석 결과 load다. rs와 [15:0]값을 32bit로 확장시킨 것을 더하고 4-2로 간다.(execute)

4-1. rs와 rt의 연산 결과를 rd에 쓴다. 그 후 1로 돌아가서 다음 명령을 기다린다(Writeback)

4-2 rs와 [15:0]확장시켜 나온 주소값에 있는 것을 읽어내고 5로 간다.(memory access)

5 읽어낸 값을 rt에 집어넣고 1로 돌아간다(Writeback)

실제로는 여러 명령어가 있는 만큼 더 복잡해지지만 일단 이런 명령어들을 각각의 상태, 레지스터의 쓰기권한을 키느냐, 메모리 접근을 가능하게 하느냐, 점프를 하게하느냐, 같은 상태값을 표현한 순서도를 구현하는 느낌이다. 이 쪽은 순서도와는 다르게 Start는 있어도 End는 없지만.