Systolic architectures are designed by using linear mapping techniques on regular dependence graphs (DG). Systolic architectures have a space-time representation where each node is mapped to a certain processing element (PE) and is scheduled at a particular time instance. Chapter 7 will discuss the systolic architecture design, inviting you refer. | Chapter 7: Systolic Architecture Design Keshab K. Parhi • Systolic architectures are designed by using linear mapping techniques on regular dependence graphs (DG). • Regular Dependence Graph : The presence of an edge in a certain direction at any node in the DG represents presence of an edge in the same direction at all nodes in the DG. • DG corresponds to space representation à no time instance is assigned to any computation ⇒ t=0. • Systolic architectures have a space-time representation where each node is mapped to a certain processing element(PE) and is scheduled at a particular time instance. • Systolic design methodology maps an N-dimensional DG to a lower dimensional systolic architecture. • Mapping of N-dimensional DG to (N-1) dimensional systolic array is considered. Chap. 7 2 • Definitions : d1 Ø Projection vector (also called iteration vector), d = d 2 Two nodes that are displaced by d or multiples of d are executed by the same processor. p T = ( p1 p2 ) ØProcessor space vector, Any node with index IT=(i,j) would be executed by processor; i pT I = ( p1 p 2 ) j ØScheduling vector, sT = (s1 s2). Any node with index I would would be executed at time, sTI. ØHardware Utilization Efficiency, HUE = 1/|STd|. This is because two tasks executed by the same processor are spaced |STd| time units apart. ØProcessor space vector and projection vector must be orthogonal to each other ⇒ pTd = 0. Chap. 7 3 Ø If A and B are mapped to the same processor, then they cannot be executed at the same time, ., STIA ≠ STIB, ., STd ≠ 0. Ø Edge mapping : If an edge e exists in the space representation or DG, then an edge pTe is introduced in the systolic array with sTe delays. Ø A DG can be transformed to a space-time representation by interpreting one of the spatial dimensions as temporal dimension. For a 2-D DG, the general transformation is described by i’ = t = 0, j’ = pTI, and t’ = sTI, ., i' i 0 j ' = T j
