NDLI: Scheduling precedence graphs to minimize total system time in partitionable parallel architectures

Content Provider	IEEE Xplore Digital Library
Author	Hyeong-Ah Choi Narahari, B.
Copyright Year	1990
Description	Author affiliation: Dept. of Electr. Eng. & Comput. Sci., George Washington Univ., Washington, DC, USA (Hyeong-Ah Choi; Narahari, B.)
Abstract	Two issues are introduced into the scheduling problem: each of the sub-tasks can be performed using one of a number of parallel algorithms running on different configurations; and there is an overhead time to move data (reconfiguration time) from the configuration required by one algorithm to the configuration required by the algorithm of the successor sub-task. The execution time for each algorithm and the reconfiguration times between all pairs of algorithms are provided along with the precedence graph. The problem is to find for each sub-task the algorithm to be executed such that the total system time, which is the sum of the execution times and the data movement times of all the selected algorithms, is minimized. The authors show that the problem is NP-hard even when the total degree, of each node of the precedence graph is at most three. They show that it can be solved in polynomial time if the total degree of each node is at most two, thus completely closing the gap between the polynomially solvable cases and the NP-hard cases in terms of the maximum degree of the precedence graph.
Starting Page	407
Ending Page	410
File Size	452596
Page Count	4
File Format	PDF
ISBN	0818620870
DOI	10.1109/SPDP.1990.143574
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1990-12-09
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Parallel architectures Partitioning algorithms Processor scheduling Parallel algorithms Parallel processing Polynomials Concurrent computing Scheduling algorithm Process control Control systems
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Algorithm for scheduling independent jobs on partitionable hypercubes

Scheduling on parallel processing systems using parallel primitives

Scheduling independent tasks on partitionable hypercube multiprocessors

Task Scheduling on the PASM Parallel Processing System

Bin-packing adjustable rectangles and applications to task scheduling on partitionable parallel computers

Dynamic critical path scheduling parallel programs onto multiprocessors

A scalable time-sharing scheduling for partitionable distributed memory parallel machines

Static scheduling of dependent parallel tasks on heterogeneous clusters

Reliability and Scheduling on Systems Subject to Failures

Scheduling precedence graphs to minimize total system time in partitionable parallel architectures

Similar Documents

Algorithm for scheduling independent jobs on partitionable hypercubes

Scheduling on parallel processing systems using parallel primitives

Scheduling independent tasks on partitionable hypercube multiprocessors

Task Scheduling on the PASM Parallel Processing System

Bin-packing adjustable rectangles and applications to task scheduling on partitionable parallel computers

Dynamic critical path scheduling parallel programs onto multiprocessors

A scalable time-sharing scheduling for partitionable distributed memory parallel machines

Static scheduling of dependent parallel tasks on heterogeneous clusters

Reliability and Scheduling on Systems Subject to Failures

Scheduling precedence graphs to minimize total system time in partitionable parallel architectures