Newsgroups: comp.parallel From: chokchai@mcs.kent.edu (Chokchai Leangsuksun) Subject: Summary: Task mapping/scheduling for Het Proc env Organization: Kent State University Date: 21 Mar 1994 23:32:38 GMT Dear Madam/Sir 2-3 weeks ago, I posted an article looking for pointers to task mapping/scheduling for heterogeneous computing environment. Several people kindly sent me thier list of papers and/or pointers to related works. Some sent me thier papers. Before I start listing, I'd like to express my gratitude to Steve Chapin, Santosh Pande, Honbo Zhou, Shlomit Pinter, Cho Sang-Young, Steve Hammond, Marco Morazan, Craig Schlenter, and Talbi El-ghazali for contributing to this list. My apologies to all who contributed but whom I've forgotten to thank. Thanks again to all who contributed. Chokchai Leangsuksun chokchai@mcs.kent.edu p.s. I have browsed thru some in the list. Mosts of papers deal with mapping/scheduling. Some consider heterogeniety issues. --------------------------------------------------------------------------- Let me start with my list. Leangsuksun, C., and Potter, J. L., Designs and Experiments on Heterogeneous Mapping Heuristics, will appear in Proceeding of the eighth International Parallel Processing Symposium Workshop on Heterogeneous Computing, Cancun, Mexico, April 1994. Leangsuksun, C., and Potter, J. L., Problem Representations for An Automatic Mapping Algorithm on Heterogeneous Processing Environments, Proceeding of the Seventh International arallel Processing Symposium Workshop on Heterogeneous Computing, Newport Beach, CA, April 1993. ------------------------------- Kim, J. S., "A General Approach to Multiprocessor Scheduling", Ph.D. Thesis, Department of Computer Sciences, The University of Texas at Austin, February 1988. Lo, V. M., "Algorithms for Static Task Assignment and Symmetric Contraction In Distributed Computing Systems", Proceeding of the 1989 International Conference On Parallel Processing, IEEE Computer Society, pp. 239-244 Lo, V. M., "Heuristic Algorithms for Task Assignment in Distributed Systems", Technical Report CIS-TR-86-13, Department of Computer and Information Science, University of Oregon, April 15, 1987. Menasce, D. A., Porto, S C. S., and Tripathi, S. K., "Processsor Assignment in Hetergeneous Parallel Architectures", Proceeding of the Sixth International Parallel Processing Symposium, Bevery Hills, CA, March 1992, pp. 186-191. Wang, M., Kim, S., Nichols, M. A., Freund, R. F., Siegel, H. J.,and Nation, W. G., "Augmented the Optimal Selection Theory for Superconcurency", Proceeding of the Sixth International Parallel Processing Symposium Workshop on Heterogeneous Computing, Bevery Hills, CA, March 1992. Freund, R. F., "Optimal Selection Theory for Superconcurency", Proceeding of Supercomputing 89, Reno, Nevada, November 1989. Freund, R. F., Conwell, D. S., "Superconcurency: A Form of Distributed Heterogeneous Supercomputing", Supercomputing Review, October 1990. Freund, R. F., Siegel, H. J., "Heterogeneous Processing", IEEE Computer, Vol. 26, No. 6, June 1993. Bhagirath Narahari, Abdou Youssef, and Hyeong-Ah Choi,"Matching and Scheduling in a Generalized Optimal Selection Theory",will appear in Proceeding of the eighth International Parallel Processing Symposium Workshop on Heterogeneous Computing, Cancun, Mexico, April 1994. Mary Eshaghian, Ying-Chieh Wu, Jose C. DeSouza-Batista, Alice C. Parker, Shiv Prakash , "A Sub-Optimal Assignment of Application Tasks onto Heterogeneous Systems", will appear in Proceeding of the eighth International Parallel Processing Symposium Workshop on Heterogeneous Computing, Cancun, Mexico, April 1994. --------------------------------------------------------------------------- contributed by Steve Chapin sjc@mcs.kent.edu S.J. Chapin and E. H. Spafford, "An Overview of the MESSIAHS Distributed Scheduling Support System. Technical Report TR-93-011, Department of Computer Sciences, Purdue University, January 1993 S.J. Chapin and E. H. Spafford, "Scheduling Support for an Internetwork of Heterogeneous, Autonomous Processors", Technical Report TR-92-006, Department of Computer Sciences, Purdue University, January 1992 ---------------------------------------------------------------------------- contributed by Honbo Zhou H. Zhou, "Distributed Computing of Weak and Strong Precedence Contrained Problems", PhD thesis, University of Zurich, 1993 H. Zhou, "Two-tage M-Way Graph Partitioning", Parallel Computing, no. 19, p. 1359-1373, 1993. -------------------------------------------------------------------------- contributed by Shlomit Pinter The following paper may be helpful to you: @article(pinter, author="Pinter, S. and Wolfstahl, Y.", title="On Mapping Processes to Processors in Distributed Systems", journal="International Journal of Parallel Programming", number="1", volume="16", pages="1--15", year="1987") More on scheduling issues you can find in the next paper. Note that we also have a longer and more elaborate paper called Partitioning and Scheduling to Contract Overhead (it was sent to a journal and I can send you a copy). @inproceedings(HP-icpp, author="Hardon, R. and S. S. Pinter", title="Choosing the Right Grains for Data Flow Machines", booktitle="International Conference on Parallel Processing", year="1991", pages="I672--I673") -------------------------------------------------------------------------- contributed by Cho Sang-Young sycho%core.kaist.ac.kr@daiduk.kaist.ac.kr The following references may be the papers we want. @article {tantawi, author = "Asser N. Tantawi and Don Towsley" , title = "Optimal Static Load Balancing in Distributed Computer" , journal = jacm , year = 1985 , month = apr , volume = "32" , number = 2 , pages = "445--465" , } @article {stankovic, author = "J. A. Stankovic" , title = "An Application of Bayesian Decision Theory to Decentralized Contral of Job Scheduling" , journal = ieeetc , year = 1985 , month = feb , volume = "C-34" , number = 2 , pages = "117--130" , } @article {wang, author = "Y. Wang and R. Morris" , title = "Load Sharing in Distributed Systems" , journal = ieeetc , year = 1985 , month = mar , volume = "C-34" , number = 3 , pages = "204--217" , } @article {shivaratri, author = "Miranjan G. Shivaratri and Phillip Krueger and Mukesh Singhal", title = "Load Distributing for Locally Distributed Systems", journal = "IEEE Computer", year = 1992 , month = dec , volume = 25 , number = 12 , pages = "33--44" , } @article {kremien, author = "Orly Kremien and Jeff Kramer" , title = "Methodical Analysis of Adaptive Load Sharing Algorithms" , journal = ieeepds , year = 1992 , month = nov , volume = "PDS-3" , number = 6 , pages = "747--760" , } @article {xu, author = "Jian Xu and Kai Hwang", title = "Mapping Rule-Based Systems onto Multicomputers Using Simulated Annealing", journal = jpdc , year = 1991 , volume = "13" , pages = "442-454" , } @conference {hwang, author = "Kai Hwang and Jian Xu" , title = "Efficient Allocation of Partitioned Program Modules in a Message-Passing Multicomputer", booktitle = "Proc. ISSM International Conf. on Paral. and Distr. Compu. and Syste." , year = 1990 , pages = "226--239" , } @article {bultan, author = "Tevfik Bultan and Cevdet Anknat" , title = "A New Mapping Heuristic Based on Mean Field Annealing" , journal = jpdc , year = 1992 , volume = "16" , number = 4 , pages = "292-305" , } @article {chleecad, author = "Cheol-Hoon Lee and Chan-Ik Park and Myunghwan Kim" , title = "Efficient Algorithm for Graph Partitioning Problem Using a Problem Transformation Method" , journal = "Computer-Aided Design" , year = 1989 , month = dec , volume = "21" , number = 10 , pages = "611--618" , } @article {gerasoulis, author = "Apostolos Gerasoulis and Tao Yang" , title = "On the Granularity and Clustering of Directed Acyclic Task Graphs" , journal = ieeepds , year = 1993 , month = jun , volume = "PDS-4" , number = 6 , pages = "686--701" , } @book {sarkar, author = "Vivek Sarkar" , title = "Partitioning and Scheduling Parallel Programs for Multiprocessors" , publisher = "The MIT Press" , year = 1989 , } @article {synthesis, author = "Insup Lee and David Smitley" , title = "A Synthesis Algorithm for Reconfigurable Interconnection Networks", journal = ieeetc , year = 1988 , month = jun , volume = "C-37" , number = 6 , pages = "691--699" , } @techreport {dime, author = "Roy Williams" , title = "DIME: Distributed Irregular Mesh Environment" , month = feb , year = 1990, institution = "California Institute of Technology" , } @article {HC_Gha93, author = "A. Ghafoor and J. Yang" , title = "A Distributed Heterogeneous Supercomputing Management System" , journal = "IEEE Computer" , year = 1993 , month = jun , volume = "26" , number = 6 , pages = "78--86" , } @conference {HC_Fre89, author = "R. F. Freund" , title = "Optimal Selection Theory for Superconcurrency", booktitle = "Proc. of Supercomputing '89" , year = 1989 , pages = "699--703" , } @conference {HC_Wan, author = "M. Wang and others" , title = "Augmenting the Optimal Selection Theory for Superconcurrency", booktitle = "Proc. of Workshop on Heterogeneous Processing" , year = 1992 , pages = "13--22" , } @article {hypertool, author = "Min-You Wu and Daniel D. Gajski" , title = "Hypertool: A Programming Aid for Message-Passing Systems" , journal = ieeepds , year = 1990 , month = jul , volume = "PDS-1" , number = 3 , pages = "330--343" , } @article {sih, author = "Gilbert C. Sih and Edward A. Lee" , title = "Declustering: A New Multiprocessor Scheduling Technique" , journal = ieeepds , year = 1993 , month = jun , volume = "PDS-4" , number = 6 , pages = "625--637" , } @article {kasahara, author = "Hironori Kasahara and Seinosuke Narita" , title = "Paractical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing" , journal = ieeetc , year = 1984 , month = nov , volume = "C-33" , number = 11 , pages = "1023--1029" , } @conference {yang, author = "Jiyuan Yang and Lubomir Bic and Alexandru Nicolau" , title = "A Mapping Strategy for MIMD Computers" , booktitle = "Proc. Inter. Conf. Parallel Processing" , year = 1991 , pages = "I-102--109" , } @article {stonetwo, author = "Harold S. Stone" , title = "Multiprocessor Scheduling With the Aid of Network Flow Algorithms" , journal = ieeese , year = 1977 , month = jan , volume = "SE-3" , number = 1 , pages = "85--93" , } @article {sadaynnm, author = "Ponnuswamy Sadayappan and Fikret Ercal" , title = "Nearest-Neighbor Mapping of Finite Element Graphs onto Processor Meshes" , journal = ieeetc , year = 1989 , month = dec , volume = "C-36" , number = 12 , pages = "1408--1424" , } @article {bowen, author = "Nicholas S. Brown and Christos N. Nikolaou and Arif Ghafoor", title = "On the Assignment Problem of Arbitrary Process Systems to Heterogeneous Distributed Computer Systems" , journal = ieeetc , year = 1992 , month = mar , volume = "C-41" , number = 3 , pages = "257--273" , } @article {shatz, author = "Sol M. Shatz and Jia-Ping Wang and Masanori Goto" , title = "Task Allocation for Maximizing Reliability of Distributed Computer Systems" , journal = ieeetc , year = 1992 , month = sep , volume = "C-41" , number = 9 , pages = "1156--1168" , } @article {bokhadyn, author = "Shahid H. Bokhari" , title = "Dual Processor Scheduling with Dynamic Reassignment" , journal = ieeese , year = 1979 , month = jul , volume = "SE-5" , number = 4 , pages = "341--349" , } @article {nicoldyn, author = "David M. Nicol and Paul F. Reynolds, JR" , title = "Optimal Dynamic Remapping of Data Parallel Computations" , journal = ieeetc , year = 1990 , month = feb , volume = "C-39" , number = 2 , pages = "206--219" , } @article {origin, author = "Wesley W. Chu and Leslie J. Holloway and Min-Tsung Lan and Kemal Efe" , title = "Task Allocation in Distributed Data Processing" , journal = "IEEE Computer" , year = 1980 , month = nov , volume = "13" , number = 11 , pages = "57--69" , } @article {stonecon, author = "Harold S. Stone and S. H. Bokhari" , title = "Control of Distributed Processes" , journal = "IEEE Computer" , year = 1978 , month = jul , volume = "11" , number = 7 , pages = "97--106" , } @article {stonelod, author = "Harold S. Stone" , title = "Critical Load Factors in Distributed Computer Systems" , journal = ieeese , year = 1978 , month = may , volume = "SE-4" , number = 3 , pages = "254--258" , } @article {bokhatre, author = "S. H. Bokhari" , title = "A Shortest Tree Algorithm for Optimal Assignments across Space and Time in a Distributed Processor Systems", journal = ieeese , year = 1981 , month = nov , volume = "SE-7" , number = 6 , pages = "583--589" , } @article {towsley, author = "D. F. Towsley" , title = "Allocating Programs Containing Branches and Loops within a Multiple Processor System" , journal = ieeese , year = 1986 , month = oct , volume = "SE-12" , number = 10 , pages = "1018--1024" , } @article {ktree, author = "D. Fernandez-back" , title = "Allocating Modules to Processors in a Distributed System" , journal = ieeese , year = 1989 , month = nov , volume = "SE-15" , number = 11 , pages = "1427--1436" , } @article {lo, author = "V. M. Lo" , title = "Heuristic Algorithms for Task Assignment in Distributed Systems" , journal = ieeetc , year = 1988 , month = nov , volume = "C-37" , number = 11 , pages = "1384--1397" , } @article {chleelin, author = "Cheol-Hoon Lee and Dongmyun Lee and Myunghwan Kim" , title = "Optimal Task Assignment in Linear Array Networks" , journal = ieeetc , year = 1992 , month = jul , volume = "C-41" , number = 7 , pages = "877--880" , } @article {sychohyp, author = "Sang-Young Cho and Cheol-Hoon Lee and Myunghwan Kim" , title = "Optimal Task Assignment in Hypercube Networks" , journal = "Tr. on the IEICE" , year = 1992 , month = apr , volume = "E75" , number = 4 , pages = "504--511" , } @article {arora, author = "R. K. Arora and S. P. Rana" , title = "Heuristic Methods for Process Assignment in Distributed Computing Systems" , journal = "Information Processing Lett." , year = 1980 , month = dec , volume = "11" , pages = "199--203" , } @article {efe, author = "K. Efe" , title = "Heuristic Models of Task Assignment Scheduling in Distributed Systems" , journal = "IEEE Computer" , year = 1982 , month = jun , volume = "15" , number = 6 , pages = "50-56" , } @article {ercalhyp, author = "F. Ercal and J. Ramanujan and P. Sadayappan" , title = "Task Allocation onto a Hypercube by Recursive Mincut Bipartitioning" , journal = jpdc , year = 1990 , volume = "10" , pages = "35-44" , } @article {sinclair, author = "J. B. Sinclair" , title = "Efficient Computation of Optimal Assignments for Distributed Tasks" , journal = jpdc , year = 1987 , volume = "4" , pages = "342-362" , } @article {cvetanovic, author = "Zarka Cvetanovic" , title = "The effects of Problem Partitioning, Allocation, and Granularity on the Performance of Multiple-Processor Systems" , journal = ieeetc , year = 1987 , month = apr , volume = "C-36" , number = 4 , pages = "421-432" , } @article {berger, author = "Marsha J. Berger and Shahid H. Bokhari" , title = "A Partitioning Strategy for Nonuniform Problems on Multiprocessors" , journal = ieeetc , year = 1987 , month = may , volume = "C-36" , number = 5 , pages = "570-580" , } @article {bokhapar, author = "S. H. Bokhari" , title = "Partitioning Problems in Parallel, Pipelined and Distributed Computing" , journal = ieeetc , year = 1988 , month = jan , volume = "C-37" , number = 1 , pages = "48-57" , } @article {hansen, author = "Pierre Hansen and Keh-Wei Lih" , title = "Improved Algorithms for Partitioning Problems in Parallel, Pipelined and Distributed Computing" , journal = ieeetc , year = 1992 , month = jun , volume = "C-41" , number = 6 , pages = "769-771" , } @conference {chleelod, author = "Cheol-Hoon and Dongmyun Lee and Chan-Ik Park and Myunghwan Kim" , title = "An Efficient $k$-way Graph Partitioning Algorithm for Task Allocation in Parallel Computing Systems" , booktitle = "Proc. 1st Int. Conf. in Syst. Integr." , year = 1990 , pages = "748--751" , } @article {shenminm, author = "C. C. Shen and W. H. Tsai" , title = "A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minmax Criterion" , journal = ieeetc , year = 1985 , month = mar , volume = "C-34" , number = 3 , pages = "197-203" , } @article {bokhamap, author = "S. H. Bokhari" , title = "On the Mapping Problem" , journal = ieeetc , year = 1981 , month = mar , volume = "C-30" , number = 3 , pages = "207-214" , } @article {leemap, author = "Soo-Young Lee and J. K. Aggarwal" , title = "A Mapping Stretegy for Parallel Processing" , journal = ieeetc , year = 1987 , month = apr , volume = "C-36" , number = 4 , pages = "433-442" , } @article {waynemap, author = "S. Wayne Bollinger and Scott F. Midkiff" , title = "Heuristic Technique for Processor and Link Assignment in Multicomputers" , journal = ieeetc , year = 1991 , month = mar , volume = "C-40" , number = 3 , pages = "325-333" , } ------------------------------------------------------------- contributed by Steve Hammond hammond@ncar.ucar.edu @phdthesis{hammond92, author = "S. W. Hammond", title = "Mapping Unstructured Grid Problems to Massively Parallel Computers", school = "Rensselaer Polytechnic Institute", address = "Troy, New York", month = "May", year = "1992" } available as TR92.14 from Deanna deanna@riacs.edu ------------------------------------------------------------- contributed by Andy Ben-Dyke (A.D.Ben-Dyke@computer-science.birmingham.ac.uk) @TechReport{Application:Scheduling, author = {Kennet C. Sevcik}, title = {Application Scheduling and Processor Allocation in Multiprogrammed Parallel Processing}, institution = {University of Toronto}, year = {1993}, number = {CSRI-282}, month = {March}, email = {kcs@csri.toronto.edu}, ftp = {ftp.csri.toronto.edu:/csri-technical-reports/282/282.ps}, annote = {The paper is concerned with application scheduling in parallel processing systems, so as to keep average response time low. Starts with an overview of the scheduling issues (classification based on objective, felxibility, arrival process, service demand knowledge, structure and priority, as well as static/dynamic techniques). Notes that that a number of studies strongly recommend that only one processor should be assigned to each application, maximising useful computation and therefore total throughput.}, got = {yes}, } ----------------------------------------------- contributed by --Craig Schlenter (cschle@elaine.ee.und.ac.za) Try looking at "A Compile-Time Scheduling Heuristic for Interconnection- Constrained Heterogenous Processor Architectures" - Gilbert Sih and Edward Lee, IEEE Transactions on Parallel and Distributed Systems, Vol 4, no.2, Feb 1993. ----------------------------------------------- contributed by TALBI EL-GHAZALI ghazali@imag.fr This file is the README file of the directory pub/SYMPA on imag.fr (129.88.32.1) This directory contains different papers (technical reports, conference and journal articles, theses, monographies, etc...) written by members of the SYMPA team of the LGI laboratory in Grenoble, France. Our adress is: SYMPA/LGI - Institut IMAG BP 53 38041 Grenoble Cedex FRANCE Fax: (33)76.44.66.75 E-mail: muntean@imag.fr CONTENT _______ This directory contains PostScript files. The detail content of these files is described in the TABLE-OF-CONTENT file. The TABLE-OF-CONTENT file is made of a list of items (one per paper) containing the following information. ******************************************************************** TITLE : AUTHOR(S) : REFERENCE : LANGUAGE :either "english" or "french" LENGTH :number of pages DATE :date when the file was put in the present directory KEYWORDS : FILE NAME : Author E-mail : Related Files : ABSTRACT : ******************************************************************** The TABLE-OF-CONTENT file is an ascii text file and may be obtained through FTP to be exploited using your favorite editor. The order is a reverse chronological order, the most recently placed paper being at top in the TABLE-OF-CONTENT A paper xxx.yyy.e.ps.Z is written in English, while a paper xxx.yyy.f.ps.Z is written in French. HOW TO RETRIEVE A FILE FROM HERE? _________________________________ To retrieve a file xxx.yyy.e.ps.Z : Anonymous ftp on: - imag.fr or - 129.88.32.1 yourmachine>ftp imag.fr Name: anonymous Password: yourname@youradress ftp>cd pub/SYMPA ftp>binary %THIS IS IMPERATIVE as the files are in compressed format% ftp>get xxx.yyy.e.ps.Z ftp>quit yourmachine>uncompress xxx.yyy.e.ps.Z yourmachine>lpr -ls xxx.yyy.e.ps PROBLEMS ________ Any PostScript problem should be reported directly to the author. Any other problem may be reported to ghazali@imag.fr ******************************************************************** TITLE :General heuristics for the mapping problem AUTHOR(S) :E-G.Talbi, T.Muntean REFERENCE :World Transputer Congress, IOS Press, Aachen, Germany,Sep93 LANGUAGE :English LENGTH :13 DATE :20/09/93 KEYWORDS :Genetic algorithms, Simulated annealing, Hill-climbing, Mapping problem FILE NAME :talbi.WTC93.e.ps.Z Author E-mail :ghazali@imag.fr muntean@imag.fr Related Files :talbi.TSI91.f.ps.Z, talbi.RenPar93.f.ps.Z, talbi.HPC91.e.ps.Z ABSTRACT : Hill-climbing, simulated annealing and genetic algorithms are general search techniques that can be applied to most combinatorial optimization problems. In this paper, the three algorithms are used to solve the mapping problem: optimal static allocation of communicating processes on distributed memory parallel architectures. Each algorithm is independently evaluated and optimized according to its parameters. The parallelization of the algorithms is also considered. As an example, a massively parallel genetic algorithm is proposed for the problem, and results of its implementation on a 128-processor SuperNode (reconfigurable network of transputers) are given. A comparative study of the algorithms is then carried out. The criteria of performances considered are the quality of the solutions obtained and the amount of search timeused for several benchmarks. A hybrid approach consisting in a combination of genetic algorithms and hill-climbing is also proposed and evaluated. ***************************************************************************** ******************************************************************** TITLE :Parallel motion planning with the Ariadne's clew algorithm AUTHOR(S) :E.Mazer, J.M.Ahuactzin, E-G.Talbi, P.Bessiere, T.Chatroux REFERENCE :Int. Conf. on Experimental Robotics ISER-93, Kyoto, Japan LANGUAGE :English LENGTH : DATE :31/01/94 KEYWORDS :robot motion planning, genetic algorithms, parallel algorithms FILE NAME :talbi.ISER93.e.ps.Z Author E-mail :mazer@lifia.imag.fr ghazali@imag.fr Related Files :talbi.ECAI92.e.ps.Z, talbi.IROS93.e.ps.Z ABSTRACT : We describe an implementation of a real time path planner for a robot arm with six degrees of freedom moving among dynamical obstacles. The planner is based on a novel technique called the Ariadne's Clew Algorithm. A brief description of this algorithm and parallel implementation of it are presented. Finally we analyze experiments made with this planner. ******************************************************************** ******************************************************************** TITLE :Allocation dynamique et migration de processus dans le le systeme parallele PAROS AUTHOR(S) :A.Elleuch, T.Muntean, E-G.Talbi REFERENCE :5iemes Rencontres du Parallelisme, Brest LANGUAGE :French LENGTH :4 DATE :May 1993 KEYWORDS :Migration de processus, allocation dynamique, Systeme parallele FILE NAME :talbi.RenPar93.f.ps.Z Author E-mail :elleuch@imag.fr muntean@imag.fr ghazali@imag.fr Related Files :talbi.LT91.f.ps.Z ABSTRACT : Le systeme PAROS a ete concu pour des architectures massivement paralleles, c'est pourquoi nous avons tenu a decentraliser l'algorithme d'allocation dynamique des taches. Chaque processeur, de la meme maniere que les autres processeurs, participe a la distribution de la charge dans son propre voisinage Ceci permet de limiter les couts de traitement et de communication pour le maintien de l'etat des processeurs voisins, la localisation d'un processeur en petite charge, et le transfert ou la migration d'une tache. Conscient que la migration de processus est une operation couteuse, nous avons elabore un algorithme d'allocation ou en premier lieu, la distribution de charge se fait lors du placement initial des taches en tenant compte de l'etat du systeme. cette strategie, si elle n'offre pas dans certains cas une bonne distribution de la charge, reduit tout au moins le recours a la migration des taches utilisees en dernier ressort. **************************************************************************** ******************************************************************** TITLE :THE "ARIADNE'S CLEW" ALGORITHM Global planning with local methods AUTHOR(S) :Pierre Bessiere, Juan-Manuel Ahuactzin, El-Ghazali Talbi & Emmanuel Mazer REFERENCE :IEEE-IROS'93 conference, Yokohama, Japan, 1993 LANGUAGE :English LENGTH :8 pages DATE :28/09/93 KEYWORDS :Robotic, Parallel Genetic Algorithm, Path planning FILE NAME :talbi.IROS93.e.ps.Z Author E-mail :Pierre.Bessiere@imag.fr ghazali@imag.fr Related Files :talbi.ECAI92.e.ps.Z, talbi.ISER93.e.ps.Z ABSTRACT : The goal of the work described in this paper is to build a path planner able to drive a robot in a dnamic environment where the obstacles are moving. In order to do so, we propose a method, called "Ariadne's clew algorithm", to build a global path planner based on the combination of two local planning algorithms : an Explore algorithm and a Search algorithm. The purpose of the Explore algorithm is to collect information about the environment with an increasingly fine resolution by placing landmarks in the searched space. The goal of the Search algorithm is to opportunistically check if the target can be easily reached from any given placed landmark. The Ariadne's clew algorithm is shown to be very fast in most cases allowing plannning in dynamic environments. Hence, it is shown complete, which means that it is sure to find a path when one exists. Finally, we describe a massively parallel implementation of this algorithm. ******************************************************************** ******************************************************************** TITLE :Etude experimentale d'algorithmes de placement AUTHOR(S) :El-Ghazali Talbi REFERENCE :Lettre du Transputer et des Calculateurs distribues vol.15, pp.7-26 LANGUAGE :French LENGTH :19 DATE :Sep 1992 KEYWORDS :Algorithmes iteratifs, Algorithmes genetiques, Recuit simule, Placement statique de processus. FILE NAME :talbi.LT93.f.ps.Z Author E-mail :ghazali@imag.fr Related Files : ABSTRACT : Les algorithmes iteratifs de recherche locale, le recuit simule et les algorithmes genetiques sont des algorithmes de recherche qui peuvent etre appliques a la plupart des problemes d'optimisation combinatoire. Dans cet article, un exemple d'application de ces algorithmes est presente: le probleme de placement statique de processus communicants sur une architecture parallele a memoire distribuee. Les problemes classiques de partitionnement de graphes et d'affectation quadratique ne sont qu'une instance du probleme traite. Chacun des algorithmes etudies est evalue et optimise en fonction de ses parametres. La parallelisation des algorithmes est aussi analysee ; un algorithme genetique massivement parallele est propose, et est mis en oeuvre sur un reseau de transputers. Une comparaison des performances des differents algorithmes est effectuee, suivant la qualite de la solution trouvee et le temps de recherche utilisee. Enfin, une combinaison des algorithmes est proposee et evaluee. ******************************************************************** ******************************************************************** TITLE :Using genetic algorithms for robot motion planning AUTHOR(S) :J.M. Ahuactzin, E-G Talbi, P. Bessiere & E. Mazer REFERENCE :ECAI92, Vienna, Austria, 1992 LANGUAGE :English LENGTH :5 DATE :31/01/94 KEYWORDS :robot motion planning, genetic algorithms, parallel algorithms. FILE NAME :talbi.ECAI92.e.ps.Z Author E-mail :jma@lifia.imag.fr ghazali@imag.fr Related Files : talbi.ISER93.e.ps.Z talbi.IROS93.e.ps.Z ABSTRACT : We present an ongoing research work on robot motion planning using genetic algorithms. Our goal is to use this technique to build fast motion planners for robot with six or more degree of freedom. After a short review of the existing methods, we will introduce the genetic algorithms by showing how they can be used to solve the invers kinematic problem. In the second part of the paper, we show that the path planning problem can be expressed as an optimization problem and thus solved with a genetic algorithm. We illustrate the approach by building a path planner for a planar arm with two degree of freedom, then we demonstrate the validity of the method by planning paths for an holonomic mobile robot. Finally we describe an implementation of the selected genetic algorithm on a massively parallel machine and show that fast planning response is made possible by using this approach. ******************************************************************** ******************************************************************** TITLE :Methodes de placement de processus sur architectures paralleles AUTHOR(S) :T.Muntean, E-G. Talbi REFERENCE :Technique et Science Informatique TSI, Vol.10, No.5 pp.355-373, Nov 1991 LANGUAGE :French LENGTH :18 DATE :Nov 1991 KEYWORDS :Placement statique, Heuristiques, Systemes massivement parallele, Programmation mathematique FILE NAME :talbi.TSI91.f.ps.Z Author E-mail :muntean@imag.fr ghazali@imag.fr Related Files :talbi.HPC91.e.ps.Z talbi.WTC93.e.ps.Z ABSTRACT : Les performances d'un programme execute sur une architecture parallele dependent fortement du placement des processus composant le programme sur les divers processeurs. Le placement laisse entierement a la charge du programmeur est souvent dependant de l'application et de la machine. Le placement automatique de processus permet entre autres une programmation transparente de l'architecture cible, et la portabilite des programmes entre les divers structures de communication des architectures parallles. Ce type de placement peut etre statique ou dynamique. Cet article traite du placement automatique statique pour lequel une analyse critique et une etude comparative des differents travaux effectuees dans ce domaine sont presentees. Nous proposons aussi une classification des algorithmes d'allocation suivant les modeles utilises dans la formulation du probleme et les strategies utilisees pour le resoudre. Enfin, nous degageons les divers limitations d'un placement statique de processus. ******************************************************************** ******************************************************************** TITLE :A Parallel Genetic Algorithm for process-processors mapping AUTHOR(S) :T.Muntean, E-G.Talbi REFERENCE :2nd Symposium on High Performance Computing, Edited by El-dabaghi, North-Holland, Montpellier, France LANGUAGE :English LENGTH :11 DATE :Oct 1991 KEYWORDS :Genetic algorithmes, parallel algorithm, mapping problem FILE NAME :talbi.HPC91.e.ps.Z Author E-mail :muntean@imag.fr ghazali@imag.fr Related Files :talbi.WTC93.e.ps.Z ABSTRACT : Genetic algorithms are general purpose optimization and search techniques based on biological principles, that maneuver through complex spaces in a near optimal way. This paper addresses an application of genetic algorithms to the mapping problem: the placement of communicating processes on a parallel distributed memory architecture. A population of individuals representing possible solutions is maintained. Search proceeds by applying genetic operators on individuals of the population. Standard genetic algorithms with large populations suffer from lack of efficiency (quite long execution time). A massively parallel genetic algorithm is proposed, an implementation on a reconfigurable transputer network and results of various benchmarks are given. ******************************************************************** ******************************************************************** TITLE :Un algorithme d'allocation dynamique de processus sur un reseau de transputers AUTHOR(S) :El-Ghazali TALBI REFERENCE :Lettre du Transputer et des Calculateurs Distribues vol.11, pp.7-20, Sep 1991. LANGUAGE :French LENGTH :13 DATE :Sep 1991 KEYWORDS :Allocation dynamique, Reseau de transputers, Systeme parallele FILE NAME :talbi.LT91.f.ps.Z Author E-mail :ghazali@imag.fr Related Files : ABSTRACT : Dans la conception de systemes d'exploitation pour des machines paralleles, l'allocation des processus composant un programme possede un impact critique sur les performances globales du systeme. Apres analyse et critique des methodes d'allocation dynamiques presentees dans la litterature, un algorithme independant de la taille et de la topologie du reseau est propose. L'algorithme realise un compromis entre exploiter le parallelisme de la paire architecture/ programme et reduire le cout de communication dans le reseau. L'algorithme presente est distribue, i.e chaque processus execute le meme processus d'allocation ; il prend en compte l'etat courant du systeme sans utiliser a priori des informations sur les caracteristiques des processus ; stable, il evite l'ecroulement du systeme ; non preemptif et simple. Une extension de l'algorithme pour des architectures heterogenes a aussi ete propose. Un programme de simulation en vue de l'evaluation de l'algorithme a ete implante sur un reseau de transputers, et des resultats preliminaires sont presentes. ******************************************************************** ******************************************************************** TITLE :A PARALLEL GENETIC ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM AUTHOR(S) :E-G. Talbi & P. Bessiere REFERENCE :ACM-ICS91 (International Conference on Supercomputing) Cologne, Gremany, 1991 LANGUAGE :English LENGTH :9 DATE :28/09/93 KEYWORDS :Genetic Algorithm, Parallel algorithm, Graph partitioning FILE NAME :talbi.ACM91.e.ps.Z Author E-mail :ghazali@imag.fr Pierre.Bessier@imag.fr Related Files :talbi.LT93.f.ps.Z talbi.WTC93.e.ps.Z ABSTRACT : Genetic algorithms are stochastic search and optimization techniques which can be used for a wide range of applications. This paper addresses the application of genetic algorithms to the graph partitioning problem. Standard genetic algorithms with large populations suffer from lack of efficiency (quite high execution time). A massively parallel genetic algorithm is proposed, an implementation on a SuperNode of Transputers and results of various benchmarks are given. The parallel algorithm shows a superlinear speed-up, in the sense that when multiplying the number of processors by p, the time spent to reach a solution with a given score, is divided by kp (k>1). A comparative analysis of our approach with hill-climbing algorithms and simulated annealing is also presented. The experimental measures show that our algorithm gives better results concerning both the quality of the solution and the time needed to reach it. ----------------------------------------------------------------------- contributed by Santosh Pande \bibitem{hawaii93} Pande S. S., Agrawal D. P., and Mauney J., ``A Fully Automatic Compiler For Distributed Memory Machines", {\it Proc. Of The 26th Hawaii International Conference On System Sciences}, January 1993, pp. 536-545. \bibitem{tpds} Pande S. S., Agrawal D. P., and Mauney J., ``A Scalable Scheduling Scheme For Functional Parallelism on Distributed Memory Multiprocessor Systems", {\it IEEE Transactions on Parallel and Distributed Systems} (To appear). \bibitem{jpdc} Pande S. S., Agrawal D. P., and Mauney J., ``A New Threshold Scheduling Strategy for Sisal Programs on Distributed Memory Machines", {\it Journal of Parallel and Distributed Computing.}\\ (To appear).\\ ----------------------------------------------------------- contributed by Marco Morazan Models of Machines and Computation for Mapping in Multicomputers Michael G. Norman & Peter Thanisch ACM Computing Surveys, Vol. 25, No. 3, September 1993 -- Regards, Chokchai Leangsuksun Heterogeneous Processing Research Group Department of Mathematics and Computer Science Kent State University Kent Ohio 44242 e-mail: chokchai@mcs.kent.edu (internet)