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 Field  Value  Language 
dc.contributor.author  Ravikumar, C P   
dc.contributor.author  Vedi, Naresh   
dc.date.accessioned  20050408T10:50:45Z   
dc.date.available  20050408T10:50:45Z   
dc.date.issued  1995   
dc.identifier.citation  Microprocessing and Microprogramming ,(41) 137151  en 
dc.identifier.uri  http://eprint.iitd.ac.in/dspace/handle/123456789/135   
dc.description.abstract  We 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 nearoptimal 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 divideandconquer 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.extent  1109759 bytes   
dc.format.mimetype  application/pdf   
dc.language.iso  en   
dc.subject  Mapping  en 
dc.subject  Scheduling  en 
dc.subject  Reconfigurable processors  en 
dc.subject  Neural optimization  en 
dc.subject  Boltzmann machines  en 
dc.title  Heuristic and Neural Algorithms for Mapping Tasks to a Reconfigurable Array  en 
dc.type  Article  en 
Appears in Collections:  Electrical Engineering

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