AN MIN-BASED ARCHITECTURE FOR RECONFIGURABLE DE BRUIJN STRUCTURES

作     者：S. SRINIVAS K. THULASIRAMAN M.N.S. SWAMY 

作者机构：Department of Electrical and Computer Engineering Concordia University Montreal Quebec H3G 1M8 Canada Present address: Division of Computing Department of Mathematics Statistics and Computing Science Dalhousie University Halifax Nova Scotia B3H 3J5 Canada. 

出 版 物：《International Journal of High Speed Electronics and Systems》 

年 卷 期：1992年第3卷第3N04期

页      面：279-296页

学科分类：0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

摘      要：This paper presents a novel parallel architecture based on a multistage interconnection network (MIN) for reconfigurable binary de Bruijn structures. The proposed architecture is able to assume distinct binary de Bruijn configurations (BDCs), where each configuration has the geometric pattern or structure as that of a binary de Bruijn graph. A system with N nodes or processing elements can generate N 2 /4 distinct BDCs. The novelty of the architecture is in the design of the switching network for interconnecting the nodes. The switching network adopted is an augmented shuffle-exchange MIN. The favorable features of the architecture include fast reconfiguration, simplified hardware in the MIN, absence of the need for reconfiguration hardware in the nodes, and simple routine control. The generation of BDCs is derived from an equation, called the Reconfiguration Equation, which is based on simple logical operations and defines the necessary interconnections among the nodes. It is shown that the architecture assumes interconnections according to this equation and consequently the proof of reconfiguration is given. The important properties of the reconfigurable de Bruijn structure are outlined. Finally, two features which are useful in enhancing the reconfigurability of the architecture are discussed. First, it is proved that the architecture can be augmented to generate partitioned de Bruijn configurations. Second, it is shown that the architecture can assume distinct binary tree configurations by a simple modification.