EPrints@IIT Delhi >
Faculty Research Publicatons  >
Electrical Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/135

Full metadata record

DC FieldValueLanguage
dc.contributor.authorRavikumar, C P-
dc.contributor.authorVedi, Naresh-
dc.identifier.citationMicroprocessing and Microprogramming ,(41) 137-151en
dc.description.abstractWe consider the problem of mapping tasks onto processors in a reconfigurable array architecture. We assume a directed acyclic task graph as input. The node weights in the task graph represent their computational requirement; the weight on an edge (i, j) is an estimate of the communication requirement between tasks i and j. The problem is to (a) estimate the minimum number of processors p to execute all the tasks with the highest possible efficiency, (b) bind each task to a processor, (c) schedule the tasks within each processor, and (d) carry out link allocation among processors. We assume a realistic model of reconfigurable parallel processors, where each processor can be connected to at most d other processors through bidirectional links. The objective of the problem is to minimize the total overall execution time, which includes the time spent by the processors in computation, communication, and idling. The mapping problem is computationally hard, and we present two algorithms for obtaining near-optimal solutions. The fiit algorithm is a heuristic algorithm based on the critical path method and as soon IIS possible scheduling. The second algorithm uses the Boltzmam~ machine model of artificial neural networks to solve the mapping problem. We have implemented both the algorithms on a Sun/SPARC workstation. Experimental results on a set of benchmark problems indicate that the neural algorithm generates better solutions than the heuristic algorithm, but takes significantly larger amounts of time than the latter. The number of neurons required in the algorithm is equal to n.p and hence the connection matrix is np X np; thus the neural algorithm is also memory intensive and I/O intensive due to swapping. We have devised a parallel divide-and-conquer algorithm which decomposes a large mapping problem into several smaller ones and solves the subproblems concurrently on a network of Sun workstations.en
dc.format.extent1109759 bytes-
dc.subjectReconfigurable processorsen
dc.subjectNeural optimizationen
dc.subjectBoltzmann machinesen
dc.titleHeuristic and Neural Algorithms for Mapping Tasks to a Reconfigurable Arrayen
Appears in Collections:Electrical Engineering

Files in This Item:

File Description SizeFormat
ravheu95.pdf1.08 MBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback