[go: up one dir, main page]

Kim et al., 1994 - Google Patents

A two-pass scheduling algorithm for parallel programs

Kim et al., 1994

Document ID
5550777361387612900
Author
Kim D
Yi B
Publication year
Publication venue
Parallel Computing

External Links

Snippet

In this paper a fast task scheduling algorithm is proposed. An optimal task scheduling assigns tasks to processors such that the overall completion time (makespan) of a given task is minimized. To find an optimal task scheduling is known NP-complete. The proposed …
Continue reading at www.sciencedirect.com (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Programme initiating; Programme switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5061—Partitioning or combining of resources
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/52—Programme synchronisation; Mutual exclusion, e.g. by means of semaphores; Contention for resources among tasks
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/30—Arrangements for executing machine-instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline, look ahead
    • G06F9/3885—Concurrent instruction execution, e.g. pipeline, look ahead using a plurality of independent parallel functional units
    • G06F9/3889—Concurrent instruction execution, e.g. pipeline, look ahead using a plurality of independent parallel functional units controlled by multiple instructions, e.g. MIMD, decoupled access or execute
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformations of program code
    • G06F8/41—Compilation
    • G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/76—Architectures of general purpose stored programme computers

Similar Documents

Publication Publication Date Title
Kwok et al. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors
US6230303B1 (en) Proximity-based cluster allocation for hardware-software co-synthesis of heterogeneous distributed embedded systems
US6097886A (en) Cluster-based hardware-software co-synthesis of heterogeneous distributed embedded systems
Ahmad et al. On parallelizing the multiprocessor scheduling problem
Bleuse et al. Scheduling independent moldable tasks on multi-cores with GPUs
Baruah Partitioned edf scheduling: a closer look
Huang et al. Task ranking and allocation in list-based workflow scheduling on parallel computing platform
Sih Multiprocessor scheduling to account for interprocessor communication
Kim et al. A two-pass scheduling algorithm for parallel programs
Huang et al. Communication-aware task scheduling algorithm for heterogeneous computing
Atef et al. Lower-bound complexity algorithm for task scheduling on heterogeneous grid
Kwok et al. Exploiting duplication to minimize the execution times of parallel programs on message-passing systems
Cosnard et al. Compact dag representation and its symbolic scheduling
Yusuf et al. Energy aware parallel scheduling techniques for network-on-chip based systems
Li PARALLEL PROCESSING OF COMBINATORIAL SEARCH PROBLEMS (DIVIDE-AND-CONQUER, BRANCH-AND-BOUND, LOGIC PROGRAMMING, DYNAMIC)
He et al. Algorithms for tree-shaped task partition and allocation on heterogeneous multiprocessors: S. He et al.
Ma et al. A dynamic load balancer for a parallel branch and bound algorithm
Sanders et al. Efficient parallel scheduling of malleable tasks
Mrabet et al. A clustering allocation and scheduling analysis approach for multiprocessor dependent real-time tasks
Chen et al. A heterogeneous multicore co-scheduling algorithm based on multi-characteristic fuzzy cluster
Yu-Kwong Efficient algorithms for scheduling and mapping of parallel programs onto parallel architectures
Atif System Software support for distributed real-time systems
Norman et al. Models of machines and modules for mapping to minimise makespan in multicomputers
Park Dynamic processor partitioning for multiprogrammed multiprocessor systems
Eswari et al. A path priority-based task scheduling algorithm for heterogeneous distributed systems