Section 10

10.1    BRANCHED PROGRAMS

10.1.1     A program may be divided into branches which are regarded as independent programs from the point of view of the time-sharer.  By setting up branches to deal with peripheral transfers for instance the efficiency of a program may be significantly increased.  The branching of a program may, however, easily give rise to program mistakes and must be used with caution.

10.1.2     Setting up a branch

A branch is set up by means of a special 150 instruction

i.e.   150   X   Y   24

This instruction means:-

Set up a branch which I shall refer to as branch X and set its entry address equal to Y.  If branch X already exists make it jump to Y.

X is a small integer lying between 1 and 7 but if this is the first branch to be set up then X must not be equal to 1 and in this case the original program is regarded as branch 1.

New branches are initially switched off, waiting for the branch which set them up.

10.1.3     Reservations

Each program in the machine needs a directory entry of at least 16 words and when a new branch is set up the space for this is taken from the highest available region of the programs reservations, which are accordingly reduced.  In addition to this, 8 words must be allowed for the branch directory, where the monitor program keeps details of the branch relationships.  (i.e. interlocks)  In general, a program intending to have n branches should request at least l6n-8 additional working store locations.

All the branches of a program are given the same core, drum and peripheral reservations, thus allowing information dumped by one branch to be picked up by another and also allowing branches to communicate by means of common markers.

10.1.4    Timing

The actions of the various branches are synchronised by means of the fast special 150 instruction

150   X   Y   2

The precise action of this instruction is shown in the following flow diagram

This instruction must not be premodified and replacement would usually make it prohibitively slow.

Generally speaking the action is to switch on branch X if it is waiting and to switch off this branch if y < 0.  There are two exceptions.

(i)  If X is switched off waiting for another branch the effect is to switch it on but to subtract one from its control number, so that it will again obey the 150/2 which caused it to switch itself off.  This allows one to deal satisfactorily with cases where several branches may alter the condition on which another branch switches itself off.

(ii) Y=0.  This is a special case.  The effect is to switch off this branch, waiting for X, unless X is switched off waiting for this branch.  The use of this special form is illustrated in the example which follows in 10.1.6.

The normal form of the 150/2 instruction (Y0) should usually be followed by a guard jump, i.e.

150   X   Y   2
 64  -1+  Y

This is necessary to guard against a particular sequence of events which could cause a branch to go although its count (y) is negative (see.10.1.6).

 

10.1.5     Multiple buffering

A distinctive feature of branched programs is the way in which buffers are dealt with (“buffer” here simply means a region of the store where information is dumped by one branch and picked up by another).  If, for instance, a branch is reading in cards it will usually have several buffers and will fill them cyclically.  If there are 4 buffers each of 20 words the branch must use a modifier taking successively the values 0, 20, 40, 60, 0, 20 and so on.  The branch which deals with this information must have a similar but independent modifier.  In addition two counters must be kept, one indicating the number of buffers left available to the input program and the other indicating the number of buffers to be dealt with.  The sum of these two counts in this example will be the number of buffers less 2, their initial values depending on the actual program.

 

10.1.6      Example

Suppose that a program can be conveniently divided into 3 branches which we will call for convenience, INPUT, COMPUTE and OUTPUT.

INPUT (branch 2) will read in a file from magnetic tape and at some stage detect an end of file marker.

COMPUTE (branch l) will process this data and will use OUTPUT (branch 3) to print out the results on a line printer.  We will suppose, for simplicity, that there are 4 input and 4 output buffers.

The necessary organisational instructions are as follows. (They are given more concisely in the appendix).

150     2     INPUTE      24
150     3     OUTPUTE     24

(Call the input and output branches 2 and 3 respectively and set their entry points equal to INPUTE and OUTPUTE).

 14     IC1     3
 13     IC2     1

(Set initial values of input counts).

 13     OC1     1
 14     OC2     3

(Set initial values of output counts).

COMPUTEE)
150     2      IC2     2
 64    -1+     IC2

(Switch on INPUT if it is waiting.  Switch this branch off if IC2m < 0 i.e. there is no data to process).

Process next buffer

 10     IC1     1
 11     IC2     1
 10     OC1     1
 11     OC2     1

(Deal with counters.  Note that each branch steps down the counts which appear in its 150s and steps up the associated count).

150     3     OC2     2
 64    -1+    OC2

(Switch on OUTPUT if it is waiting.  Switch off this branch if OC2m<0 i.e. all the output buffers are full).

Jump to COMPUTEE

E)
150     3     0     2
 65    -1+   OC1

(Switch off this branch until OUTPUT switches it on and simultaneously switches itself off, i.e. wait until all output buffers have been emptied.  The control number E+1 is set by the input branch).

Deal with end of file.

INPUTE)   Read into next buffer.

 10     IC2     1
 11     IC1     1
150      1     IC1     2
 64     -1+    IC1

(Switch on Computing branch if waiting for this one.  If it is switched off waiting for OUTPUT, switch it on but subtract 1 from its control number, i.e. make it obey 150    3    OC2    2 again.  Switch  off this branch if IC1m < 0  i.e. all input buffers are full).

Jump to INPUTE if not end of file.

150      1       0     2
 65     -1+     IC2

(Switch off this branch until COMPUTE switches it on and simultaneously switches itself off, i.e. wait until all the input buffers have been dealt with),

150     1     E+1     24

(Set control number of COMPUTE.  Note that it is set as E+l and not E, in case there is an interruption at this point and OUTPUT gets in and switches it on.)

150     1     0+     2

(Switch on COMPUTE and switch off INPUT, waiting for COMPUTE).

OUTPUTE)  Print next buffer

 10    OC2     1
 11    OC1     1
150     1     OC1    2
 64    -1+    OC1

(Switch on COMPUTE if it is waiting for this branch.  If it is waiting for INPUT, switch it on but subtract 1 from its control number, i.e. make it obey 150  2  IC2  2 again.  Switch off this branch if Oclm<0, i.e there is nothing to output).

Jump to OUTPUTE

 

When the instruction labelled COMPUTEE is first obeyed it will switch on INPUT and switch off COMPUTE, waiting for INPUT.  The input branch will then be entered at INPUTE and after reading in a buffer of data it will switch on COMPUTE again.  This will then process one buffer of information and switch on OUTPUT.  The 150/2 instructions in this program ensure that each of the branches is switched on whenever possible, and at the same time ensure that one branch does not get ahead of the others.

The necessity for the guard jumps can be seen by considering the following sequence.

COMPUTE is interrupted when it is just about to obey the instruction 150  2  IC2  2.

INPUT is entered, proceeds until it has filled the last available buffer and switches itself off because IC1 has become negative.

COMPUTE is now entered and immediately switches on INPUT.

The instruction 150  X  0  2 means switch off this branch, waiting for X unless X is switched off waiting for this branch.  By using this instruction followed by suitable conditional jumps, it is possible, as illustrated here, to shut down all but one branch and thus bring the program into a standard, known condition, when special events may satisfactorily be dealt with.  Which control paths to close will obviously vary with the program and the method given here is not necessarily the best.

 

10.1.7    Special points about branched programs

  1. A program failure in or any OMP monitoring action for or any 150 instruction for, any branch causes OMP to hold up (suspend) all branches whilst OMP carries out its action.

  2. A 150/10 (see 5.3.10) in any branch causes all branches to be stopped in the same mode.

    If the whole program has been halted e.g. after a 150/10 then it will be started by a RUN directive for the branch which caused the halting, and will be in the same state as it was in, before the halting occurred, so far as branch interlocks are concerned.

  3. The simplest way of making a branch shut down itself is to write
    150    X    0    2
    where X is the number of the branch itself.  It cannot then be switched on by any of the other branches unless they reset its control number.  There is a danger when using this device of losing all the control paths.

  4. The instruction 150/11 in any branch will immediately cause the whole program to be abolished.

  5. Each branch has its own time, new branches being allotted one minute as they are set up.  Timing flags (150/1) in a branch apply to that branch alone.

  6. Different branches may monitor the same event in different styles.  It is insanitary for two branches to monitor the same event in style 7 with the same jump address.

 

10.1.8    Branch names and directives

When a branch is set up it is given a job name composed of the original job name together with the branch number e.g. BLOGGS2.  The original job name alone, typed with a directive will be taken to apply to branch 1 or, by implication, to all branches, e.g. BLOGGS HALT will halt all branches.  The name BLOGGS1 is illegal.  The directives which need a branch number are MONITOR, OUTPUTON and ANSWER and TIME.  All other directives apply, implicitly, to the whole program.

A RERUN (see 5.3.10 and 5.7.2.2) directive will be accepted if a branch has obeyed 150  0  2  10 instruction which causes OMP to temporarily unbranch the program (i.e. the branch interlocks are remembered and all branches are switched off awaiting Branch 1).  If it is desired to restore the branch interlocks a 150/25 may be used.

ENTER (with link) directive (see 5.3.25 and 5.7.3.4) causes OMP to “push down” and to temporarily unbranch the program and to use Branch 1’s control number as the link which is stored in the accumulator, say L, and to enter the routine this being Branch 1.  A 150/25 in the enter routine is used to return and restore conditions e.g. 150  L  0  25 means pull up, restore previous branch interlocks and set control number for this branch to [L]m and OVR according to [L]s and current state of OVR.  Any previous pushing down and temporarily unbranched state are remembered.

ENTER (without a link) causes no “pushing down” and causes OMP to switch off all branches awaiting Branch 1 and to forgot any temporarily unbranched state and any previous “pushing down”.  ENTER is allowed for branch 1 only.

 

10.1.9      Peripheral Incidents in branched programs

Peripheral incidents may be set dynamically by any branch of a program, but the setting is taken to apply to the program as a whole.  If the incident occurs, OMP records the program as being “pushed down”, and temporarily unbranches the program.  If the link is required it uses Branch 1’s control number.  Any previous “pushing down” and temporarily unbranched state is remembered.  The routine to deal with the incident should normally end with a 150/25 instruction which will pull up and return, restoring the conditions to what they were before the incident occurred.  For more details see 5.3.25.

 

Appendix to 10.1

Example of branched program given in 10.1.6

Four input buffers and four output buffers.

IC1m + 1 = no. of buffers available to INPUT.  IC2m + 1 = no. of buffers awaiting processing by COMPUTE.  OC1m + 1 = no. of buffers awaiting to be output.  OC2m + 1 = no. of output buffers available to COMPUTE.

COMPUTE (Branch 1)

 

150

2

INPUTE

24

 

150

3

OUTPUTE

24

 

14

IC1

3

 

 

13

IC2

1

 

 

13

OC1

1

 

 

14

OC2

3

 

COMPUTEE)

150

2

IC2

2

 

64

-1+

IC2

 


Process next buffer

 

10

IC1

1

 

 

11

1C 2

1

 

 

10

OC1

1

 

 

11

OC2

1

 

 

150

3

OC2

2

 

6k

-1+

OC2

 

 

75

COMPUTEE

0

 

E)

150

3

0

2

 

65

-1+

OC1

 


Deal with end of file
      

INPUT (Branch 2)

OUTPUT (Branch 3)

 

INPUTE) Read into next buffer  

OUTPUTE) Print next buffer

 

 

10

IC2

1

 

 

10

OC2

 

 

11

IC1

1

 

 

11

OC1

1

 

 

150

1

IC1

 2

 

150

1

OC1

2

 

64

-1+

IC1

 

 

64

-1+

OC1

 

 Jump to INPUTE if not end of file

 

75

OUTPUTE

 0

 

 

150

1

0

2

 

65

-1+

IC2

 

 

150

1

E+l

24

 

150

1

0+

2