전가산기와 가감가산기, PIPELINE 조사

소개

Least Laxity Algorithm과 전가산기와 가감가산기, 그리고 Pipeline에 대해 조사하고, 보고서를 작성하였습니다.

목차

1. 「Least Laxity Algorithm」

1.1 「Least Laxity First For Real Time System」

2. 「전가산기와 가감가산기」

2.1 전가산기

2.2 가감가산기

3. Pipeline

3.1 Pipeline의 원리

3.2 Pipeline 처리로 인한 속도 증가
3.2.1 Pipeline 속도
3.2.2 Non-Pipeline 속도
3.2.3 Pipeline 속도 증가율

3.3 파이프라인의 문제점
3.3.1 자원 충돌(Resource Conflict)
3.3.2 데이터의존성(Data Dependancy)
3.3.3 분기 곤란(Branch Difficulty)

본문내용

1. 「Least Laxity Algorithm」
1.1 「Least Laxity First For Real Time System」
Real Time System은 원격통신, 멀티미디어, 미사일 추적, 자동화 시스템, 산업용 로봇, 항공 제어 등의 여러 분야로 확대 응용되고 있다. 이 시스템의 정확성이 논리적 정확성뿐만 아니라 결과를 마감시간(Dead Line)에 맞추는 시간적 정확성이 크게 작용하는 시스템이다.
RTOS(Real time OS)에서 사용하는 Real time scheduling은 task가 마감시간에 맞추어 실행될 수 있도록 task를 프로세서에 할당하는 역할을 하며, 이는 RTOS에 시간적 정확성 제공하는 중요한 부분이다. Real time scheduling algorithm은 Preemptive하고 동적인 우선순위(Dynamic priorities-실행 시 task의 우선순위가 시간에 따라 변함)를 가져야 한다. 이 두 가지를 가진 scheduling algorithm으로 Least Laxity First algorithm과 Earliest Deadline First algorithm이 있다.
Least Laxity First algorithm은 multiprocessor에서 최적화되어 최고의 CPU utilization을 보인다. Least Laxity First scheduling algorithm은 여유시간이 적은 task가 높은 우선순위를 갖는 동적 우선순위 scheduling 방법이다. 여유시간이란 task가 시간 t부터 선점 당하지 않는다고 가정하고 수행을 마쳤을 때 마감시간까지의 여분시간을 말한다.
임의의 시간 t에서 task의 상태는 task의 Deadline까지 남은 Deadline : Di(t)와 task가 수행 종료하기까지 남은 잔여 수행시간(remaining execution time) : Ei(t)로 나타내었을 때 여유시간 ; Li(t)는 다음과 같이 나타낸다.

참고자료

· 없음