Title :
Optimal reconfiguration of WSI multipipeline arrays
Author :
Salinas, J. ; Feng, C. ; Wall, J. ; Lombardi, F.
Author_Institution :
Dept. of Comput. Sci., Texas A&M Univ., College Station, TX, USA
Abstract :
This paper presents a new algorithm for reconfiguring WSI multipipeline arrays in the presence of faults in links, processing elements (PE´s) and switching elements (SE´s). Using a fault model in which a PE and link can be either fault free or faulty and a SE is modeled by relating its switching capabilities to its status and the status of the connecting links, it is proved that an algorithm which maximizes the number of reconfigured pipelines (optimality) is possible in an execution complexity lower than a previous algorithm based on a maximum flow approach. The proposed approach is based on a greedy algorithm with an execution complexity of O(n×m), where n is the number of stages (or columns) of the array and m is the number of PE´s in a stage
Keywords :
VLSI; microprocessor chips; parallel architectures; pipeline processing; WSI multipipeline array; execution complexity; fault model; greedy algorithm; processing elements; reconfiguration; reconfigured pipelines; switching capabilities; Circuit faults; Fault tolerance; Iterative algorithms; Manufacturing processes; Pipelines; Production; Registers; Switches; Switching circuits; Very large scale integration;
Conference_Titel :
Wafer Scale Integration, 1994. Proceedings., Sixth Annual IEEE International Conference on
Conference_Location :
San Francisco, CA
Print_ISBN :
0-7803-1850-1
DOI :
10.1109/ICWSI.1994.291257
