Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1987 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Assignment Problems in Parallel and Distributed Computing

verfasst von: Shahid H. Bokhari

Verlag: Springer US

Buchreihe : The International Series in Engineering and Computer Science

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This book has been written for practitioners, researchers and stu­ dents in the fields of parallel and distributed computing. Its objective is to provide detailed coverage of the applications of graph theoretic tech­ niques to the problems of matching resources and requirements in multi­ ple computer systems. There has been considerable research in this area over the last decade and intense work continues even as this is being written. For the practitioner, this book serves as a rich source of solution techniques for problems that are routinely encountered in the real world. Algorithms are presented in sufficient detail to permit easy implementa­ tion; background material and fundamental concepts are covered in full. The researcher will find a clear exposition of graph theoretic tech­ niques applied to parallel and distributed computing. Research results are covered and many hitherto unpublished spanning the last decade results by the author are included. There are many unsolved problems in this field-it is hoped that this book will stimulate further research.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
The assignment problem is a fundamental aspect of distributed computing. It arises whenever the procedures or modules of a program are distributed over several interconnected computers so that program activity moves among processors as execution proceeds. The program may be serial (only one module active on one processor at a time) or parallel (several modules concurrently active on several processors). The assignment problem deals with the question of assigning modules to processors so as to minimize the cost of running a program. The cost may be time, money or some other measure of resource usage.
Shahid H. Bokhari
Chapter 2. Graph-Theoretic Concepts
Abstract
In this chapter we introduce the reader to those concepts from graph theory that underlie the two major approaches to the assignment problem presented in this book. As discussed briefly in the introduction, these graph theoretic concepts lend themselves very naturally to the analysis of partitioning problems on multiple computer systems. As with all introductory tracts on graph theory, we must necessarily cover a substantial number of definitions before applying these concepts in an interesting fashion. The reader comfortable with graph theoretic ideas may skip over this chapter, returning as necessary to refer to specific definitions. It is, however, important for the novice to have some familiarity with these ideas before venturing into subsequent chapters.
Shahid H. Bokhari
Chapter 3. Network Flow Techniques
Abstract
The application of network flow algorithms to assignment problems in distributed computer systems was pioneered by Harold Stone (77a). He showed how an assignment problem can be transformed into a network flow problem such that there is a one-to-one correspondence between assignments and cutsets. For the case of two processor problems, the optimal assignment—which corresponds to the minimum weight cutset—can be found very efficiently using any one of several available network flow algorithms.
Shahid H. Bokhari
Chapter 4. Shortest Path Techniques
Abstract
Efficient extensions of the network flow techniques of the previous chapter to systems made up of four or more processors are not known. However, if the graph of a modular program is constrained in certain ways, it is possible to find the optimal assignment over a system made up of any number of processors in polynomial time. When the graph is constrained to be a tree, a shortest tree algorithm developed by Bokhari (81b) yields the optimal assignment. For the case of series-parallel graphs (which we will define below) an algorithm developed by Towsley (86) can be used. Both algorithms can take the speed of each processor to processor link into account. The tree algorithm can also be used to schedule precedence graphs in a distributed system in which costs vary with time so as to minimize the total cost of execution.
Shahid H. Bokhari
Chapter 5. Varying Load Conditions
Abstract
Many distributed processing applications involve programs that run repeatedly day after day. This happens, for example, in graphics applications where a standard set of routines is used in a production environment. This is also the case in industrial process control and monitoring applications, where real-time programs execute continuously. In these cases the execution and communication costs of the various parts of the program are known accurately and an optimal assignment can be computed well before the actual running of an application.
Shahid H. Bokhari
Chapter 6. The Sum-Bottleneck Path Algorithm
Abstract
In the preceding three chapters we have seen how maximum flow and shortest path algorithms can be used to find the optimal assignment of a serial distributed program. Recent research has shown that a sum-bottleneck path algorithm can be employed to find the optimal assignment of the modules of a parallel or pipelined program in several types of distributed systems. This approach can also be used to find the optimal global assignment of a set of independent serial distributed programs over a single-host, multiple-satellite system. Since this technique can explicitly take concurrency into account, it represents a major development over the work presented in the preceding chapters.
Shahid H. Bokhari
Chapter 7. Mapping for Parallel Processing
Abstract
The assignment problems discussed so far in this book have involved the placement of the modules of a serial or parallel program on the processors of a multiple computer system. The objective when making these assignments is to minimize some measure of resource usage. Most often the objective is to minimize the total run time of a program by minimizing the sum of execution and interprocessor communication times. The modules of the distributed program could be collections of procedures, possibly individual procedures, or could be data files.
Shahid H. Bokhari
Chapter 8. Conclusions
Abstract
We begin this Chapter with a brief survey of alternative techniques for the solution of assignment problems. We then discuss the problems that remain open and the prospects for their solution. We conclude by describing the journals and conference proceedings in which the reader can find reports of recent research work on the assignment problem.
Shahid H. Bokhari
Backmatter
Metadaten
Titel
Assignment Problems in Parallel and Distributed Computing
verfasst von
Shahid H. Bokhari
Copyright-Jahr
1987
Verlag
Springer US
Electronic ISBN
978-1-4613-2003-6
Print ISBN
978-1-4612-9195-4
DOI
https://doi.org/10.1007/978-1-4613-2003-6