An Efficient Graph Embedding Algorithm for a Three-Dimensional Cellular Reconfigurable Array

スポンサーリンク

概要

• 論文の詳細を見る

• The 3-dimensional cellular reconfigurable array (abbreviated to 3-D CECOA) is a reconfigurable multiprocessing system consisting of two uniformly interconnected network of cells, one of them is a rectangular array of processing elements called the active cells (AT-cells) and the other is a 3-dimensionallattice array of switch cells (SW-cells). This paper proposes a graph embedding algorithm, based on an edge-coloring technique for bipartite graphs, which is concerned with the embedding of an arbitrary graph into 3-D CECOA, where edges of a graph are mapped to paths in the array of SW-cells and nodes of a graph are mapped to AT-cells. The proposed algorithm takes O(dn.log(dn)) time and O(dn) space and requires O((dn)^<3/2>) volume of SW-cells, where d and n are the degree and the order of the given graph. A distributed switch setting algorithm for establishing interconnection paths is called self-routing if each SW-cell determines its own setting depending on the incoming routing data. This paper also proposes a self-routing algorithm. Under this proposed self-routing algorithm, any interconnection path between AT-cells can be established using 4(log((dn)^<1/2>)+3) bits of the routing data, where d and n are the degree and the order of the given graph.

• 一般社団法人情報処理学会の論文
• 1985-10-21

著者

• Harao M

  Yamagata Univ. Yonezawa Jpn

• Harao Masateru

  Faculty Of Engineering Yamagata University

• Noguchi S

  Research Institute Of Electrical Communication Tohoku University

• Noguchi Shoichi

  Research Center For Applied Information Science Tohoku University

• PAISAN LOMTONG

  Research Institute of Electrical Communication Tohoku University

• Paisan L

  Tohoku Univ. Sendai Jpn

関連論文

• AMLOG : an Amalgamated Equational Logic Programming Language
• Limits on the Performance of Quantum-Controlled Devices
• An Improvement of The Protocol Synthesis Algorithm
• CNV Based Intermedia Synchronization Mechanism under High Speed Communication Environment
• Realization of Regular Expression Recognizers by Programmable Cellular Array
• A PROGRAM TRANSFORMATION FROM EQUATIONAL PROGRAMS INTO LOGIC PROGRAMS(Lambda Calculus and Computer Science Theory)
• Generalized Predicate Completion and its Relation to Circumscription
• A Partial Translation of Default Logic to Circumscription
• Can Completion Entail Circumscription (Sometimes)?
• Classification of the NOAA Satellite Image Data by Unsupervised Neural Network
• An Efficient Graph Embedding Algorithm for a Three-Dimensional Cellular Reconfigurable Array
• A Canonical Translation from Higher Order Logic to Typed Lambda Calculus
• A Real-Time Scheduler Using Neural Networks for Scheduling Independent and Nonpreemptable Tasks with Deadlines and Resource Requirements

もっと見る 閉じる

スポンサーリンク