Abstract
In a multiprocessor array, some processing elements (PEs) fail to function normally due to hardware defects or soft faults caused by overheating, overload or occupancy by other running applications. Fault-tolerant reconfiguration considered in this paper is to reorganize fault-free PEs from a processor array with faults to a logical array of regular mesh topology by changing the interconnections among PEs. This paper presents the efficiency of the flexible rerouting scheme to maximize the usage of the fault-free PEs, by developing an efficient reconfiguration algorithm without backtracking. The proposed algorithm constructs each logical columns from left to right on candidate PE sets. It updates the candidate sets by excluding the PEs which cannot be used, once a logical column is formed. Also, it is proved that the proposed heuristic algorithm is able to generate the maximum-size logical array in linear time. Experimental results show that 123 logical columns can be constructed on 256 ×256 host arrays with fault density of 30%, resulting in an improvement of 51% in comparison to the previous algorithm by which only 82 logical columns can be produced. Furthermore, our algorithm is able to generate target arrays with harvest over 56% on host arrays with fault density of 50%, while the previous work cited in this paper fails to construct any target array in this case.
Chapter PDF
Similar content being viewed by others
References
Murali, S., De Micheli, G.: SUNMAP: A tool for automatic topology selection and generation for NoCs. In: Proc. of the 41st Design Automation Conference (DAC 2004), pp. 914–919. ACM Press, San Diego (2004)
Bertozzi, D., Jalabert, A., Murali, S., Tamahankar, R., Stergiou, S., Benini, L., De Micheli, G.: NoC synthesis flow for customized domain specific multiprocessor systems-on-chip. IEEE Transactions on Parallel and Distributed System 16(2), 113–129 (2005)
Modarressi, M., Sarbazi-Azad, H.: Power-aware mapping for reconfigurable NoC architectures. In: Proc. of the 25th International Conference on Computer Design, pp. 417–422. IEEE Press, California (2007)
Modarressi, M., Tavakkol, A., Sarbazi-Azad, H.: Application-Aware Topology Reconfiguration for On-Chip Networks. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 19(11), 2010–2022 (2011)
Chen, Y.Y., Upadhyaya, S.J., Cheng, C.H.: A comprehensive reconfiguration scheme for fault-tolerant VLSI/WSI array processors. IEEE Transactions Computers 46(12), 1363–1371 (1997)
Horita, T., Takanami, I.: Fault-tolerant processor arrays based on the 1.5-track switches with flexible spare distributions. IEEE Transactions on Computers 49(6), 542–552 (2000)
Kuo, S.Y., Chen, I.Y.: Efficient reconfiguration algorithms for degradable VLSI/WSI arrays. IEEE Transactions Computer-Aided Design 11(10), 1289–1300 (1992)
Low, C.P., Leong, H.W.: On the reconfiguration of degradable VLSI/WSI arrays. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems 16(10), 1213–1221 (1997)
Low, C.P.: An efficient reconfiguration algorithm for degradable VLSI/WSI arrays. IEEE Transactions on Computers 49(6), 553–559 (2000)
Wu, J., Srikanthan, T.: Reconfiguration Algorithms for Power Efficient VLSI Subarrays with 4-port Switches. IEEE Transactions on Computers 55(3), 243–253 (2006)
Fukushi, M., Fukushima, Y., Horiguchi, S.: A genetic approach for the reconfiguration of degradable processor arrays. In: Proc. of 20th IEEE International Symposium on Defect Fault Tolerance VLSI System, pp. 63–71. IEEE Press, Ohio (2005)
Wu, J., Srikanthan, T., Han, X.: Preprocessing and Partial Rerouting Techniques for Accelerating Reconfiguration of Degradable VLSI Arrays. IEEE Transactions on Very Large Scale Intergration (VLSI) Systems 18(2), 315–319 (2010)
Jiang, G., Wu, J., Sun, J.: Non-Backtracking Reconfiguration Algorithm for Three-dimensional VLSI Arrays. In: Proc. of 2012 IEEE 18th International Conference on Parallel and Distributed Systems, pp. 362–367. IEEE Press, Singapore (2012)
Jiang, G., Wu, J., Sun, J.: Efficient Reconfiguration Algorithm for Three-dimensional VLSI Arrays. In: Proc. of 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, pp. 254–258. IEEE Press, Shanghai (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 IFIP International Federation for Information Processing
About this paper
Cite this paper
Jiang, G., Wu, J., Sun, J. (2013). Efficiency of Flexible Rerouting Scheme for Maximizing Logical Arrays. In: Hsu, CH., Li, X., Shi, X., Zheng, R. (eds) Network and Parallel Computing. NPC 2013. Lecture Notes in Computer Science, vol 8147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40820-5_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-40820-5_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40819-9
Online ISBN: 978-3-642-40820-5
eBook Packages: Computer ScienceComputer Science (R0)