Publication

Abstract : Systolic arrays are hardware structures built for fast and efficient operation of regular algorithms that perform the same task with different data at different time instants. Systolic arrays replace a pipeline structure with an array of processing elements that can be programmed to perform a common operation. Regularity, reconfigurability and scalability are some of the features of systolic design. Systolic architectures offer the competence to uphold the high-throughput capacity requirement. Multi-dimensional image processing algorithms, video streaming, nonlinear optimization problems and decision based algorithms are a few of many algorithms that are computationally demanding and can be benefited by implementing systolic arrays. To satisfy a highly held comparison parameter of computational efficiency, there exists a bottleneck of memory hierarchy. It is undeniable that hardware and software have to go hand in hand to remove the bottleneck and achieve better performance. Any regular algorithm such as matrix multiplication can be implemented in systolic architecture through mapping hardware computations to a space time transformation using a dependence graph. Systolic design methodology maps an N-dimensional dependence graph to a lower-dimensional systolic architecture using a transformation. Mapping is a process of assigning each point in iteration space a scheduled processing element for the operation at discrete time. Mapping can be done heuristically with high cost in accuracy and design time. Evolutionary algorithms act as an alternative solution for efficient search for mapping solutions. The evolutionary algorithms belong to non-traditional techniques which mimic the biological behavior of organisms to obtain the solution. They duplicate the nature of species evolution, group of ants, swarm of birds, school of fishes, groups of frogs, etc. The decision of choosing an evolutionary algorithm for the mapping process is based on its swift learning capabilities and less computation time compared to traditional random, exhaustive search procedures.