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

Title:  Heuristic and Neural Algorithms for Mapping Tasks to a Reconfigurable Array 
Authors:  Ravikumar, C P Vedi, Naresh 
Keywords:  Mapping Scheduling Reconfigurable processors Neural optimization Boltzmann machines 
Issue Date:  1995 
Citation:  Microprocessing and Microprogramming ,(41) 137151 
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. 
URI:  http://eprint.iitd.ac.in/dspace/handle/123456789/135 
Appears in Collections:  Electrical Engineering

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