The week's pick
Reseach Article
A Generic Graph-Oriented Mapping Strategy for a Honeycomb Topology
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 1 - Number 21 |
| Year of Publication: 2010 |
| Authors: Gaurav Kumar Singh, Mythri Alle, Keshavan Vardarajan, S K Nandy, Ranjani Narayan |
10.5120/39-641
|
Gaurav Kumar Singh, Mythri Alle, Keshavan Vardarajan, S K Nandy, Ranjani Narayan . A Generic Graph-Oriented Mapping Strategy for a Honeycomb Topology. International Journal of Computer Applications. 1, 21 ( February 2010), 91-98. DOI=10.5120/39-641
Abstract
REDEFINE [3] is a polymorphic ASIC, in which arbitrary com- putational structures on hardware are defined at runtime. The REDEFINE execution fabric comprises Compute Elements (CEs) interconnected by a Honeycomb network, which also serves as the distributed Network-on-chip. Each computational structure is dynamically assigned to a subset of the CEs on the execution fabric by the REDEFINE support logic. A HLL specification of the application is compiled into Hyper Operations (HyperOps) by the REDEFINE compiler [3], where each HyperOp is a set of interacting operations. The compiler also determines partitions of the HyperOps (pHyperOps) that can be assigned to CEs to suitably meet the structural constraints of the execution fabric. In this paper we propose an algorithm to map HyperOps onto Computational Structures. A pHyperOp communication graph (PCG) captures the communication between the various pHyperOps. Through a sequence of transformations, the PCG is transformed into a Cayley tree. The Cayley tree is then overlayed on the Cayley graph to form a computational structure. The proposed mapping algorithm offers a solution that incurs a penalty 18% on average over that of the optimal.
References
- B. Akers and B. Krishnamurthy. A group-theoretic model for symmetric interconnection networks, IEEE Trans. on Computers, vol. 38, pp. 555-566, 1989
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H Freema and Co, 1979
- Mythri Alle, Keshavan Varadarajan, Alexander Fell, Ramesh Reddy C, Nimmy Joseph, Saptarsi Das, Prasenjit Biswas, Jugantor Chetia, Adarsh Rao, S K Nandy. REDEFINE: Runtime Reconfigurable Polymorphic Asic, IEEE Transaction On Embedded Computing Systems, Special Issue on configuring Algorithms, Process and Architecture, 2008
- Alexander Fell, Mythri Alle, Keshavan Varadarajan, Saptarsi Das, Prasenjit Biswas, Jugantor Chetia, S K Nandy. Streaming FFT on REDEFINE-v2: An Application Architecture Design Space Exploration, to be appeared in CASES '09, 2009
- Koziris N., Romesis M., Papakonstantinou G. and Tsanakas P. An Efficient Algorithm for the Physical Mapping of Clustered Task Graphs onto Multiprocessor Architectures, Proceedings PDP 2000 Conference, pp. 406-413, Rhodes, 2000
- Zhonghai Lu, Lei Xia, Axel Jantsch. Cluster-based Simulated Annealing for Mapping Cores onto 2D Mesh Networks on Chip, ddecs, pp. 1-6, 2008 11th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, 2008
- M. E. Fisher , J. W. Essam. Rev. Mod. Phys. 42:271, 1970
- W.K. Chen and E. Gehringer. A graph-oriented mapping strategy for a hypercube, Proc. Third Conference on Hypercube Concurrent Computers and Applications. pp. 200-209, 1988
- Sarkar V. Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors, Cambridge, MA, MIT Press, 1989.
- Yang T. and Gerasoulis A. DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Transactions on Parallel and Distributed Systems,Vol.5, No.9, pp. 951-967, 1994
- Mythri Alle et al. Synthesis of Application Accelerators on Runtime Reconfigurable Hardware. In ASAP '08, Proceedings of the 19th IEEE International Conference on Application specific Systems, Architectures and Processors, July 2008
- A. N. Satrawala et al. Redefine: Architecture of a SOC Fabric for Runtime Composition of Computation Structures, In FPL '07: Proceedings of the international Conference on Field Programmable Logic and Applications, August 2007
- I. Stojmenovic. Honeycomb Networks: Topological properties and Communication Algorithms. In IEEE Trans, Parallel and Distributed Systems, vol. 8, no. 10, pp. 1036- 1042, Oct. 1997.
Index Terms
Keywords