CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the priority benefit under 35 U.S.C. § 119 of United Kingdom Patent Application No. 1717299.0, filed Oct. 20, 2017, the entire contents of which are incorporated herein by reference.

TECHNICAL FIELD

The present disclosure relates to synchronizing the workloads of multiple different tiles in a processor comprising multiple tiles, each tile comprising a processing unit with local memory. Particularly, the disclosure relates to bulk synchronous parallel (BSP) computing protocol, whereby each of a group of tiles must complete a compute phase before any of the tiles in the group can proceed to an exchange phase.

BACKGROUND

Parallelism in computing takes different forms. Program fragments may be organised to execute concurrently (where they overlap in time but may share execution resources) or in parallel where they execute on different resources possibly at the same time.

Parallelism in computing can be achieved in a number of ways, such as by means of an array of multiple interconnected processor tiles, or a multi-threaded processing unit, or indeed a multi-tile array in which each tile comprises a multi-threaded processing unit.

When parallelism is achieved by means of a processor comprising an array of multiple tiles on the same chip (or chips in the. same integrated circuit package), each tile comprises its own separate respective processing unit with local memory (including program memory and data memory). Thus separate portions of program code can be run concurrently on different tiles. The tiles are connected together via an on-chip interconnect which enables the code run on the different tiles to communicate between tiles. In some cases the processing unit on each tile may take the form of a barrel-threaded processing unit (or other multi-threaded processing unit). Each tile may have a set of contexts and an execution pipeline such that each tile can run multiple interleaved threads concurrently.

In general, there may exist dependencies between the portions of a program running on different tiles in the array. A technique is therefore required to prevent a piece of code on one tile running ahead of data upon which it is dependent being made available by another piece of code on another tile. There are a number of possible schemes for achieving this, but the scheme of interest herein is known as “bulk synchronous parallel” (BSP). According to BSP, each tile performs a compute phase and an exchange phase in an alternating manner During the compute phase each tile performs one or more computation tasks locally on tile, but does not communicate any results of its computations with any others of the tiles. In the exchange phase each tile is allowed to exchange one or more results of the computations from the preceding compute phase to and/or from one or more others of the tiles in the group, but does not yet begin a new compute phase until that tile has finished its exchange phase. Further, according to this form of BSP principle, a barrier synchronization is placed at the juncture transitioning from the compute phase into the exchange phase, or transitioning from the exchange phases into the compute phase, or both. That is it say, either: (a) all tiles are required to complete their respective compute phases before any in the group is allowed to proceed to the next exchange phase, or (b) all tiles in the group are required to complete their respective exchange phases before any tile in the group is allowed to proceed to the next compute phase, or (c) both. When used herein the phrase “between a compute phase and an exchange phase” encompasses all these options.

An example use of multi-threaded and/or multi-tiled parallel processing is found in machine intelligence. As will be familiar to those skilled in the art of machine intelligence, machine intelligence algorithms “are capable of producing knowledge models” and using the knowledge model to run learning and inference algorithms A machine intelligence model incorporating the knowledge model and algorithms can be represented as a graph of multiple interconnected nodes. Each node represents a function of its inputs. Some nodes receive the inputs to the graph and some receive inputs from one or more other nodes. The output activation of some nodes form the inputs of other nodes, and the output of some nodes provide the output of the graph, and the inputs to the graph provide the inputs to some nodes. Further, the function at each node is parameterized by one or more respective parameters, e.g. weights. During a learning stage the aim is, based on a set of experiential input data, to find values for the various parameters such that the graph as a whole will generate a desired output for a range of possible inputs. Various algorithms for doing this are known in the art, such as a back propagation algorithm based on stochastic gradient descent. Over multiple iterations the parameters are gradually tuned to decrease their errors, and thus the graph converges toward a solution. In a subsequent stage, the learned model can then be used to make predictions of outputs given a specified set of inputs or to make inferences as to inputs (causes) given a specified set of outputs, or other introspective forms of analysis can be performed on it.

The implementation of each node will involve the processing of data, and the interconnections of the graph correspond to data to be exchanged between the nodes. Typically, at least some of the processing of each node can be carried out independently of some or all others of the nodes in the graph, and therefore large graphs expose opportunities for huge parallelism.

SUMMARY

As mentioned above, a machine intelligence model representing the knowledge model and algorithmic information about how the knowledge model is used for learning and inference can generally be represented by a graph of multiple interconnected nodes, each node having a processing requirement on data. Interconnections of the graph indicate data to be exchanged between the nodes and consequently cause dependencies between the program fragments executed at the nodes. Generally, processing at a node can be carried out independently of another node, and therefore large graphs expose huge parallelism. A highly distributed parallel machine is a suitable machine structure for computation of such machine intelligence models. This feature enables a machine to be designed to make certain time deterministic guarantees.

A factor of knowledge models which is exploited in the present disclosure is the generally static nature of the graph. That is to say that the structure of nodes and graph comprising the graph does not usually change during execution of machine intelligence algorithms. The inventors have made a machine which makes certain time deterministic guarantees to optimise computation on machine intelligence models. This allows a compiler to partition and schedule work across the nodes in a time deterministic fashion. It is this time determinism which is utilised in following described embodiments for significant optimisations in designing a computer optimised to process workloads based on knowledge models.

According to one aspect of the present invention there is provided a computer program comprising a sequence of instructions for execution on a processing unit having instruction storage for holding the computer program, an execution unit for executing the computer program and data storage for holding data, the computer program comprising one or more computer executable instructions which when executed implements;a send function which causes a data packet destined for a recipient processing unit to be transmitted on a set of connection wires connected to the processing unit, the data packet having no destination identifier but being transmitted at a predetermined transmit time; anda switch control function which when executed causes the processing unit to control switching circuitry to connect a set of connection wires of the processing unit to a switching fabric to receive a data packet at a predetermined receive time.

There may be two separate instructions: a send instruction and a switch control instruction. Features of the send instruction can include that the send instruction defines a send address by defining a location in the instruction storage from which the data packet is to be sent. Alternatively, the send instruction does not explicitly define a send address but implicitly defines a registry in which the send address is held. The send instruction may define a number of packets to be sent, each packet being associated with a different transmit time. The computer program can comprise a further instruction for updating the send address in the implicitly defined register.

The computer program can include at least one further instruction which defines a memory pointer update function which updates the memory pointer identifying a memory location in the data storage for storing the data packet which is received at the recipient processing unit.

An artefact of the instruction set described herein is that it can include merge instructions, which merge functions of a transmitting processing unit and a recipient processing unit, such that the processing unit can operate as a transmitting unit and a recipient unit within a single execution cycle. One such merge instruction merges the send function with the switch control function. Another such merge instruction merges the send function and the memory pointer update function. A further merge instruction merges the send function, switch control function and memory pointer update function such that all three functions can be accomplished in a single execution cycle.

Instructions can be issued in a first bit width which matches a bit width of a fetch stage of the execution unit. Merged instructions which merge two functions can also be a first bit width. One way of implementing a merge instruction which merges three functions is for the instruction of a first bit width to identify an operand also of the first bit width. The operand implements the switch control function and the memory pointer update function.

Alternatively, an instruction which merges three functions may be of a second bit which is twice the bit width of a fetch stage of the execution unit but which is treated as a single instruction once issued.

A merge instruction format may be a common format, wherein an opcode portion designates whether it merges the send function with the memory pointer update function or the switch control function. An exchange state can hold information for the switch control function or information for the memory pointer update function, depending on the opcode portion.

The computer program can include a synchronisation instruction which generates an indication when a compute phase of the processing unit is being completed. This enables a computer program to operate in a context where the processing units form part of a barrier synchronisation protocol which has a compute phase and an exchange phase. The send instruction can be executed in the exchange phase.

The computer program can be stored on a computer readable media which is non-transmissible. Alternatively it can be implemented as a transmissible signal.

Another aspect of the invention comprises a processing unit comprising instruction storage, an execution unit configured to execute a computer program and data storage for holding data, wherein the instruction storage holds a computer program as defined above.

Another aspect of the invention comprises a computer comprising one or more die in an integrated package, the computer comprising a plurality of processing units, each processing unit having instruction storage for holding a computer program, an execution unit configured to execute the computer program and data storage for holding data, wherein the instruction storage for each processing unit holds a computer program as defined above.

