October 2000
Intermediate to advanced
288 pages
9h 22m
English
book
Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences
by Albert Y. Zomaya, Fikret Ercal, Stephan Olariu
Content preview from Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
5.2 TASK SCHEDULING AND PROBLEM FORMULATION
The increased interest in scheduling generated numerous approaches ranging from graph-theoretic methods and heuristics to simulated annealing and genetic algorithms, among others [9–11, 13, 15, 16]. Two approaches are of particular interest here: graph theoretic and genetic algorithms.
The graph-theoretic approach is used here as base line to compare with the genetic algorithm technique that we propose in this work.
5.2.1 Graph Theoretic Approach
The graph-theoretic (GT) approach is used to solve the task-allocation problem, which is a special class of task scheduling [5, 15]. The GT approach assumes that the tasks are free to reside on any processor in the system. Then, these tasks are represented as nodes in a graph. For an accurate task allocation, the scheme considers two costs: the task execution time and the intertask communication time.
- Execx(i) The execution cost of task i in assignment x. If the processing cost of task i on processor Pk is ∞ then task i cannot be processed by processor Pk.
- Commx(i,j) The intertask communication cost (ITC) involved when tasks i and j, which reside on different processors, communicate. An ITC cost of zero means no communication takes place between the two, tasks and therefore they are not connected in the graph. An ITC cost of infinity means these two nodes must be assigned to the same processor.
The objective here is to find an assignment x that minimizes the cost function:
Exec and Comm ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.