Browse Prior Art Database

Fluctuating Control Processing to Schedule Tasks on a Parallel Processor

IP.com Disclosure Number: IPCOM000079768D
Original Publication Date: 1973-Sep-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 5 page(s) / 76K

Publishing Venue

IBM

Related People

Chroust, G: AUTHOR

Abstract

The Fluctuating Control Principle is based on the assumption that a hierarchical structure can be imposed on a program: Essentially, the structure of a program is considered to be a tree, each node describing one syntactic unit.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 5

Fluctuating Control Processing to Schedule Tasks on a Parallel Processor

The Fluctuating Control Principle is based on the assumption that a hierarchical structure can be imposed on a program: Essentially, the structure of a program is considered to be a tree, each node describing one syntactic unit.

The end nodes of the tree are identified as basic units which can be immediately executed by a processor. Other nodes in the tree are called expandable units and consist, in their turn, of immediate components which are either basic or expandable (Fig. 1). When expandable units are dispatched, a pointer is transmitted to main memory. With the help of this pointer, full information on the expandable task can be retrieved. For processing, the expandable units have to be expanded into their subtasks.

Each unit is considered to be one task. Sequencing constraints exist between the subtasks of a task. If there were no sequencing constraints, all subtasks could be executed in parallel. The sequencing constraints, however, specify that certain subtasks may only be expanded or executed after other subtasks are terminated. The `execution' of an expandable task is assumed to be its expansion. The structural description of the program is further on called `Sequencing Information'. To utilize the Sequencing Information in a parallel processor, it is necessary to keep for each expandable task an account of the status of its immediate subtasks (`waiting to be started' / `started, but not terminated' / `terminated'). At any given moment the status together with the Sequencing Information specifies which subtasks may be started or expanded.

The basis of the Fluctuating Control Processor is a symmetric system of several identical processing units (PU). The principal system components and their interconnections are shown in Fig. 2. Each PU is able to execute machine instructions and to perform control functions for a task (initiating / terminating / dispatching of subtasks, ...). The different PUs communicate with each other, with main memory MS and with a special device called address directory (AD). The manner in which the sequencing constraints are expressed is of no immediate significance to the subsequent description.

Initially, the complete program is assigned as a task to one PU. This PU initializes the control necessary for the immediate subtasks. All other PUs are put into the idle state (see section d below). The following alternate actions will be taken by PUs (in that order):
a) If the PU has control of a task, and there are some basic

tasks

whose execution is not prevented by sequencing constraints, the

PU starts processing these basic tasks, updating the status

appropriately.
b) If a PU does not find a ready basic task but some ready

expandable

tasks, it dumps the current state information into main memory.

The

1

Page 2 of 5

dumped information includes, besides the status of the subtasks,

the

status of internal registers, etc. The dumped...