NDLI: Scheduling interval orders in parallel

Content Provider	IEEE Xplore Digital Library
Author	Mayr, E.W.
Copyright Year	1995
Description	Author affiliation: Inst. fur Inf., Tech. Univ. Munchen, Germany (Mayr, E.W.)
Abstract	Interval orders are partial orders defined by having interval representations. It is well known that a transitively oriented digraph G is an interval order iff its (undirected) complement G~ is chordal. We investigate parallel algorithms for the following scheduling problem: given a system consisting of a set /spl Tscr/ of n tasks (each requiring unit execution time) and an interval order < over /spl Tscr/, and given m identical parallel processors, construct an optimal (i.e. minimal length) schedule for (/spl Tscr/,<). Our algorithm is based on a subroutine for computing so-called scheduling distances, i.e. the minimal number of time steps needed to schedule all those tasks succeeding some given task t and preceding some other task t'. For a given interval order with n tasks, these scheduling distances can be computed using n/sup 3/ processors and O(log/sup 2/n) time on a CREW-PRAM. We then give an incremental version of the scheduling distance algorithm, which can be used to compute the empty slots in an optimal schedule. From these, we derive the optimal schedule, using no more resources than for the initial scheduling distance computation and considerably improving on previous work by Sunder and He (1993). The algorithm can also be extended to handle task systems which, in addition to interval order precedence constraints, have individual deadlines and/or release times for the tasks. Our algorithm is the first NC-algorithm for this problem. As another application. It also provides NC-algorithms for some graph problems on interval graphs (which are NP-complete in general).
Starting Page	20
Ending Page	28
File Size	775021
Page Count	9
File Format	PDF
ISBN	0818669306
DOI	10.1109/HICSS.1995.375481
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1995-01-03
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Processor scheduling Optimal scheduling Scheduling algorithm Helium Parallel algorithms Parallel architectures Concurrent computing Computer architecture Phase change random access memory Read-write memory
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

Parallel external memory graph algorithms

Pointers versus arithmetic in PRAMs

An optimal algorithm for the longest common subsequence problem

An optimal randomized parallel algorithm for finding connected components in a graph

A near-optimal parallel algorithm for edge-coloring outerplanar graphs

Parallel maximum matching algorithms in interval graphs

Optimal parallel algorithms for cut vertices, bridges, and Hamiltonian path in bounded interval tolerance graphs

An efficient parallel algorithm for edge-coloring of graphs

Complexity issues in the design of functional languages with explicit parallelism

Scheduling interval orders in parallel

Similar Documents

Parallel external memory graph algorithms

Pointers versus arithmetic in PRAMs

An optimal algorithm for the longest common subsequence problem

An optimal randomized parallel algorithm for finding connected components in a graph

A near-optimal parallel algorithm for edge-coloring outerplanar graphs

Parallel maximum matching algorithms in interval graphs

Optimal parallel algorithms for cut vertices, bridges, and Hamiltonian path in bounded interval tolerance graphs

An efficient parallel algorithm for edge-coloring of graphs

Complexity issues in the design of functional languages with explicit parallelism

Scheduling interval orders in parallel