Tropical algebra based framework for error propagation analysis in systolic arrays
Samo za registrovane korisnike
2013
Članak u časopisu (Objavljena verzija)
Metapodaci
Prikaz svih podataka o dokumentuApstrakt
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 iterativ...e algorithm for error propagation analysis of systolic arrays. It will be shown that the computational complexity of the proposed algorithm is reduced from O(T-3) to O(T-2), 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.
Ključne reči:
Tropical algebra / Partial error tolerance / Nanoarchitectures / Fault tolerant systems / Error propagation analysisIzvor:
Applied Mathematics and Computation, 2013, 225, 512-525Izdavač:
- Elsevier Science Inc, New York
Finansiranje / projekti:
- Inteligentni KAbinet za FIzikalnu Medicinu - IKAFIM (RS-MESTD-Technological Development (TD or TR)-32012)
- Aproksimacija integralnih i diferencijalnih operatora i primene (RS-MESTD-Basic Research (BR or ON)-174015)
- Razvoj novih informaciono-komunikacionih tehnologija, korišćenjem naprednih matematičkih metoda, sa primenama u medicini, telekomunikacijama, energetici, zaštititi nacionalne baštine i obrazovanju (RS-MESTD-Integrated and Interdisciplinary Research (IIR or III)-44006)
DOI: 10.1016/j.amc.2013.09.059
ISSN: 0096-3003
WoS: 000327765600045
Scopus: 2-s2.0-84887073317
Kolekcije
Institucija/grupa
Mašinski fakultetTY - JOUR AU - Cirić, Vladimir AU - Cvetković, Aleksandar AU - Simić, Vladimir AU - Milentijević, Ivan PY - 2013 UR - https://machinery.mas.bg.ac.rs/handle/123456789/1707 AB - 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(T-3) to O(T-2), 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. PB - Elsevier Science Inc, New York T2 - Applied Mathematics and Computation T1 - Tropical algebra based framework for error propagation analysis in systolic arrays EP - 525 SP - 512 VL - 225 DO - 10.1016/j.amc.2013.09.059 ER -
@article{ author = "Cirić, Vladimir and Cvetković, Aleksandar and Simić, Vladimir and Milentijević, Ivan", year = "2013", abstract = "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(T-3) to O(T-2), 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.", publisher = "Elsevier Science Inc, New York", journal = "Applied Mathematics and Computation", title = "Tropical algebra based framework for error propagation analysis in systolic arrays", pages = "525-512", volume = "225", doi = "10.1016/j.amc.2013.09.059" }
Cirić, V., Cvetković, A., Simić, V.,& Milentijević, I.. (2013). Tropical algebra based framework for error propagation analysis in systolic arrays. in Applied Mathematics and Computation Elsevier Science Inc, New York., 225, 512-525. https://doi.org/10.1016/j.amc.2013.09.059
Cirić V, Cvetković A, Simić V, Milentijević I. Tropical algebra based framework for error propagation analysis in systolic arrays. in Applied Mathematics and Computation. 2013;225:512-525. doi:10.1016/j.amc.2013.09.059 .
Cirić, Vladimir, Cvetković, Aleksandar, Simić, Vladimir, Milentijević, Ivan, "Tropical algebra based framework for error propagation analysis in systolic arrays" in Applied Mathematics and Computation, 225 (2013):512-525, https://doi.org/10.1016/j.amc.2013.09.059 . .