rwolski@lll-crg.llnl.gov (Richard Wolski) (09/19/90)
Greetings and salutations, I am interested in partitioning/scheduling schemes for heterogeneous multiprocessors or multicomputers. I have been attempting to collect and consume references on partitioning and scheduling (dissertation time) for NUMA (Non Uniform memory Access) multiprocessors, and so far almost everything I have seen has assumed homogeneity. I know, I know, a heterogeneous scheme is orders of magnitude more complex than a homogeneous one -- which is pretty tough at that. Still, I'd be interested in hearing about efforts in this area, or references in the literature which I could examine. For those of you who are wondering what partitioning and scheduling are (and I include myself in that category) a brief description follows. Basically, partitioning (as I see it) is the clumping together of potentially parallel operations into sequential "grains" to reduce the per instruction scheduling overhead and the communication overhead. The concept seems most applicable to dataflow or dataflow-like parallel programming schemes where a program is broken into a collection of communicating tasks. If two tasks which need to communicate are scheduled on the same processor, the cost or overhead associated with the communication is generally less than if they are scheduled on separate processors. The process of packing tasks together for a particular processor is partitioning (I think). Once a bunch of task clumps have been determined, an efficient scheduler will try and assign those clumps to processors in an optimum way with respect to some metric such as minimum overall execution time, maximum processor utilization, etc. A lot has been done with both of these problems for homogeneous multiprocessors. I have yet to see a scheme where the multiprocessor is heterogeneous (i.e. it consists of scalar processors, vector processors, graphics processors, etc.). I have seen even less for distributed systems. While load balancing (optimizing processor utilization) has been examined for distributed systems, more often than not the system is also assumed to be homogeneous. Please don't believe for a second that I think I have even approached a complete search of the literature -- I know I haven't. I'm simply hoping that some of you more knowledgeable netlanders will be able to help me shorten (optimize) the search time. Email'd responses seem to keep the bandwidth requirements lower for NetNews so keep those cards and letters coming and I'll summarize if there is any interest. Thanks for your time, hciR Rich Wolski rwolski@lll-crg.llnl.gov Lawrence Livermore Labs P.O. Box 808, L-60 Livermore, CA 94550 (415)423-8594