[VLSI] Very Large Scale Integraed Circuit

 

 

* Understanding basic operations for computer arithmetic

* Understanding signal processing techniques for VLSI architectures

 

◆ DSP system, Iteration bound

◆ Pipelining and parallel processing

◆ Retiming and unfolding technique

◆ Folding technique

 

◆ Conventional and unconventional number systems, Fast addition

◆ Binary floating-point number system

◆ Sequential algorithms for multiplication and division

◆ High-speed multiplication

◆ Fast division

 

 

 

◆ DSP system, Iteration bound

• Clock period = critical path period = cycle time = 1/clock rate
• Sample rate = throughput rate
• iteration bound[T∞] = maximum loop bound, fundamental limit on sample period
• critical path란, delay가 없는 조건에서 max. computation time
• critical path 가 sample period 최소 값이 되므로 delay(pipe register)를 달아서 critical path 값을 줄여야 DSP system의 time cost를 줄일 수 있음.
• clock period ≥ iteration bound.  (iteration bound를 줄이기 위해서 retiming을 함)
• 결과적으로, critical path를 줄이기 위해 적절한 위치에 delay를 넣고(pipelining), iteration bound를 줄이기 위해 retiming을 진행함. (pipelining이란, cutset을 통해 delay를 추가하여 critical path를 줄임)

(unfolding의 경우에는 J x T∞)

 

sample period = unfolded iteration bound / J

sample period = (1 / M*L) * clock period    (*M: pipeline stage, L: parallel stage)

 

 

iteration bound[T∞]를 계산하는 알고리즘

* LPM(Longest Path Matrix); delay를 기준으로 path를 잡음.

* MCM(Minimum Cycle Mean); edge weight를 계산해서 node가 각 delay가 되고 delay간 computation time을 계산함.

 

◆ Pipelining and Parallel processing

Pipelining

Strength

• Reduce the effective critipal path (<= sample period를 줄임)
• Reduce the sample period
• Pipe-register를 추가함으로써 동시에 처리하는 stage 갯수를 늘릴 수 있음

Weakness

• Increase the latency
• Increase the hardware cost
• Increase the number of latches

 

Parallel

Strength

• Reduce total computation time

Weakness

• Increase the cost of hardware doubles

 

◆ Retiming

strength

• Reduce the clock period
• Reduce the number of registers
• Reduce the power consumption

주어진 DFG의 shortest path를 구함.

shortest path를 구하는 방법은 2가지 (Bellman-Ford, Floyd-Warshall)

Retiming techniques

1. Cutset retiming

2. Clock period minimizing

3. Register minimization

 

clock period ≥ iteration bound

그래서 retiming을 통해 iteration bound 값을 줄여야 DFG의 clock period를 줄일 수 있음.

Retiming 그래프 그리는 법

 

 

◆ Unfolding

• delay(pipe-register) 갯수는 그대로
• throughput은 증가
• loop unrolling 이라고도 함 (loop를 풀어놓음)

J [unfolding factor] = 2

delay와 x, y를 어떻게 분배하는 지에 대한 식이 있음.

node U -> V에 w개 delay가 있음

=>  Ui -> V(i+w)%J 에 (i+w)/J 개 dely가 있음

 

 

◆ Folding

• folding factor N
• N만큼 hardware functional unit 줄임
• 대신 processing time이 증가함.