Process Allocation and Migration in Concurrent ML

Johannes Schneiders 13/2/97

\overline{1}

Overview

DML Project Proposal Approaches

• Load Balancing

• Data Parallelism

• Explicit Allocation and Migration

Primitives for Allocation and Migration in Distributed ML Work Done Discussion of Future Work

\overline{2}

DML Project Proposal

• Provide primitives which give the programmer explicit control over placement of processes on a processor.

• The same for process migration.

• Provide access to to sufficient information to exploit this control.

• Investigate system-controlled placement and migration policies.

\overline{3}

Load Balancing

Goal: Even distribution of workload among processors Static Load Balancing

• Allocation on a processor at process creation time.

• Allocation then fixed.

• Based on random distribution or round robin.

• Easy to implement, low overhead.

• Susceptible to imbalances.

\overline{4}

Dynamic Load Balancing

Adapt to changes in workload and distribution of processes. Passive strategies Idle processors ask for work.

• Amount of work moved to idle processor can vary.

• Example: GUM [Trinder96] using FISH messages.

• Little overhead if all processors have work.

• Main overhead of load balancing delegated to idle processors.

• Request messages cause unnecessary overhead during start and end phase.

Active strategies

Distribution of processes is initiated by their creators.

• Examples: diffusion scheduling (Alfalfa [Goldberg86]), bidding algorithm

• Exchange of load information needed.

• Idle processors must wait until a neighbour submits a task.

• Loaded processors are burdened with load balancing.

• Busy processors not delayed by idle neighbours.

Hybrid strategies

Combine the advantages of active and passive strategies.

• Example: LCS [LeSergent94] Determining factors for migration

• When to migrate: Load reaches a certain threshold.

• What to migrate:

“Bigger” tasks. Task with high amount of remote communication. No task which has been migrated recently.

• Where to migrate to: Close to the needed data. Where memory space is available.

Data Parallelism

Exploit programmers knowledge about the problem which is to be programmed.

Skeletons

Abstractions of well-known parallel computational forms, for example divide and conquer. (cf. Murray Cole).

Data parallel functions

• map (function, list)

• map (function, array)

• fold (function, list)

Different implementations according to requirements by the programmer.

\overline{8}

Explicit Allocation and Migration

Programmer has full control over where processes are executed.

• run (processor, function)

• migrate (processor, process)

Primitives in Distributed ML

Existing and suggested primitives to support process allocation and migration in DML.

Existing primitives

add process (process, processor) Adds process to the run-queue of processor.

Suggested primitives

run queue size (processor) Returns the length of the run-queue on processor.

remove process (processor) Removes a currently waiting process from the run-queue on processor and returns the process.

\overline{10}

Work Done

Static load balancing Round robin allocation of processes.

Dynamic load balancing Allocation of new process on least loaded processor.

Data parallel libraries ParArray Distributed Array (parMap, parModify,

parApply). ParList Distributed List (parMap, parMapAll,

parApply, parApplyAll).

\overline{11}

Discussion of Future Work

Work that could be (or should be) done to extend DML.

Explicit migration primitives Passive dynamic load balancing Library of data parallel functions

\overline{12}

Conclusion

Load distribution and load balancing can be introduced into DML on various levels. Scheduler Process Library Prototype implementations

• Centralised static load balancing

• Data-parallel function library