Tropical algebra based framework for error propagation analysis in systolic arrays

摘要

Nanotechnology is yet to come, but even now, in early stage of development it is clear that defect and fault levels will be much higher than current CMOS technology. The exact level of defect densities is unknown, but it is assumed that 1–15% on-chip resources will be defective. Novel techniques and architectures have to be devised in order for nanoelectronics to become a viable replacement for current VLSI processes. With defect rates for current VLSI processes in the range of 1 part per billion, manufacturers can afford to discard any chip that is found to be defective. However, in order to increase fabrication yield, nanotechnology requires extensive and computationally demanding analysis of defect significance. In order to simplify the analysis, in this paper we propose a mathematical framework based on tropical algebra for circuit analysis. It is more descriptive and convenient to use in graph analysis than traditional algebra. In tropical algebra, we will derive a simple iterative algorithm for error propagation analysis of systolic arrays. It will be shown that the computational complexity of the proposed algorithm is reduced from O(T3) to O(T2), where T is the number of array cells. An example of tropical algebra analysis and design of partially defect tolerant hexagonal systolic multiplier will be given, too.