Architectural Consideration of *T Join Unit

Masato Motomura

October 12, 1992

Abstract

In order to realize rapid switching between threads, hardware support for join operation, called join unit, is inevitable. In this report, realization of join unit as a special function unit in a superscalar RISC microprocessor has been considered. Several alternatives are presented including newly developed message pipelining scheme. The message pipelining enables 4 cycle join operation using only a very simple hardware. In the alternatives presented in this report, this approach would be most promising for the first version of *T implementation. Furthermore, by combining all ideas presented, it is shown that 1 cycle join operation is possible for future implementation.

This study is based on a series of discussion between Prof. Papadopoulos, Dr. Sakai and the author.

1 Introduction

*T is a multithread parallel computer using Motorolla MC88110, superscalar RISC microprocessor. The basic idea of *T is to add ability to switch quickly between threads onto conventional RISC type microprocessor which has great single thread performance [1][2].

There will be wide variations to realize *T node processor based on this idea: from adding an autonomous processor, called synchronization processor [1][2], to adding minimal hardware support for message handling. Obviously, it is a tradeoff between hardware cost (and accordingly design cost) and performance. The study described in this report positions in the middle of this wide spectrum: utilizing special function unit (SFU) allowed in MC88000 family architecture, which means without any significant modification on MC88110 itself, to realize the ability explained above.

Specifically, this report focuses on basic ideas on how to speed up join operation with hardware support. We call this hardware join unit. As join operation is exactly a synchronization between threads (please refer to Fig. 1), it is quite important to realize fast join operation in the paradigm of multithread architecture.

In the next section, loose definition of SFU and a basic idea of the join unit before this work is presented. Alternatives for the join unit are given in Section 3. Section 4 discusses most promising alternatives in regard of easiness of implementation or performance.

2 Background

2.1 SFU

Fig. 2 shows a block diagram of MC88100 and MC88200. Readers can think of MC88110 as integrating these blocks on one chip and change it into superscalar machine, i.e., double instruction issue machine (at least, it is the author’s present understanding of MC88110).

Special function unit (SFU) is indicated by a dash-dotted block in this figure. It has 2 inputs (64b each) from source 1, 2 buses and one output to a destination bus (note that actual SFU in MC88110 has 2 pairs of this I/O ports because of double instruction issuing). Obvious but important thing to note here is the connection of each block to internal buses. For example, data read from a data cache through a data unit cannot be directly given to SFU: It should be first stored into register file.

As far as constructing the join unit according to this constraints, modification caused by SFU might only be on an instruction decoder. Thus the implementation would be easy. Some of the alternatives for the join unit described in the next section obeys this constraint but some doesn’t because of an attempt to increase performance.

2.2 Join Operation without Hardware Support

As a base case, let us consider the case when there is no hardware support for join operation except for a message buffer, which stores messages from a network. Fig. 3 shows a simple hardware picture. In this and following figures, only one set of I/O buses are shown for simplicity. Possible code sequence in this case is shown in Fig. 4(a). What happens here is basically:

1. Move V and F P of a message into registers, and store V into memory,

2. Add r_{IP} and L_{D} (immediate) to calculate a target instruction pointer,

3. Load a counter for the join operation (called join counter), and branch if it is not 0 (join fail),

4. If the join has succeeded, jump to the target instruction calculated in step 2,

5. If the join has failed, subtract 1 from the join counter and store it back to memory,

6. Move IP of a next message into a register and jump to the instruction pointed.

Here, V is a 64b data, F P is a 32b frame pointer and IP is a 32b instruction pointer contained in an incoming data. Numbers added to each instruction in Fig. 4 represents above steps. This code takes 7 cycles for the join succeeded case and 8 cycles for the failed case (note: though it is not shown here, an instruction to set initial counter value is required besides this code).

Fig. 4(b) shows the critical path for this code. As is clear from this figure, a critical path is made of a long chain of data and control dependency. Furthermore, there are many idle cycles in the critical path due to load/store and jump/branch overheads. The design target of join unit is to shorten this critical path by moderate (though it is difficult to judge what is moderate) hardware support.

2.3 Original Idea for Join Unit

Fig. 5 shows the original idea for the join unit before this study. The key idea here is to implement a join cache to store join counters along with a join logic to calculate a new counter value and a target pointer. Join cache would be constructed as 32-64 lines and 128-256 bits/line. Each line of the join cache corresponds to each frame, which contains several tens of 2-bit or 4-bit counters. The join cache plays a role to erase parts of the critical path due to loading and storing a join counter, while the join logic erases those due to conditional branch and updating a counter value.

A code example is shown in Fig. 6. Join instruction make the join logic to perform following steps:

1. Read a join counter specified by CT R from a line register,

2. Calculate a new counter value and a target instruction pointer using immediate L_{D},

3. Store an instruction pointer (the one calculated in the step 2 or the IP of the next message) and a frame pointer of the next message to r_{IP} and r_{F P}, respectively.

4. Store the counter value back to the line register.

Next instruction, which is implicitly encoded with mov instruction, selects a line of the join cache according to a F P of a next message and transfer it to a line register, while storing back the line used for present join operation.

Now, we can perform join operation in 3 cycles. This performance seems to be very nice considering the fact that even an ordinal jmp instruction takes 2 cycles. But how about hardware cost? It is by no means cheap because of a join cache which requires 4k-bit to 16k-bit capacity and a rather complicated join logic which is required to execute above steps for join and next instructions in one cycles. Furthermore, design cost would be high because cache specification should be decided through extensive simulation in order to get high hit rate.

3 Alternatives

In this section, several alternatives for the join unit are investigated so that tradeoff between hardware cost and performance would become clear. First, performance effect of join cache elimination is considered. After that, 3 basic ideas are incrementally added to basic join units both without and with join cache.

3.1 Join unit without Join cache

In order to reduce hardware cost, let’s consider eliminating join cache from the join unit and observe how many cycles we lose. In this new join unit, a join counter is loaded (stored) from (to) a data cache for each join operation, explicitly controlled by instructions. Thus the join logic, whose role is only to execute steps 2 and 3 in the previous section, gets very simple compared to the organization in Fig. 5.

The code for this case is shown in Fig. 7. This code can be easily understood from the previous codes, so explanation is omitted. Here, it takes 6 cycles to handle join operation. Thus it is concluded that elimination of join cache gives rise to additional 3 cycles.

3.2 Message Pipelining

Let’s think about the way to shrink the code sequence of Fig. 7 by applying simple modification on the join logic. By closely observing the code, it can be noticed that if we could cut off the dependency between join and jmp, we could gain at least 1 cycle.

The dependency is due to the fact that the join operation so far has had to decide which instruction to jump to, an instruction pointed by a next message or a head instruction of a thread body. But there is a way to avoid making this decision, i.e., always jumping to a next message, and if the join has succeeded, making and recirculating an message which has IP for the thread body. This idea is called message pipelining.

Fig. 8 shows the idea of message pipelining. Difference against previous methods would be clear when Fig. 8 is compared to Fig. 1. One question against this method would be an overhead to handle an additional message. Since handling of this message is done in parallel with handling of another message (that’s what pipelining means), throughput is not affected. However, latency is affected by this overhead, which might be a problem when the number of messages is not enough to keep this pipeline busy. Further discussion on this point is given in Section 4.

The code sequences for the message pipelining method both for without and with join cache are shown in Fig. 9(a) and (b), respectively. The code for without join cache (abbreviated to be WOJC hereafter) shrinks from 6 to 4, while that for with join cache (abbreviated to be WJC) stays the same. The trick to shrink the WOJC code is, as described above, 1. do jump using IP of a next message, 2. move F P of a next message at the end of the code.

This WOJC code is quite attractive because there is no open slot in the code, which tells its efficiency, and the hardware to support this code is quite simple as explained in Section 4.

3.3 Adding Special Registers

The main obstacle to prevent WJC code from shrinking in the previous section is that the instructions to transfer contents of the message to registers and then to memory. In other words, these instructions now form a critical path instead of original critical path shown in Fig. 4(b). The method to decrease this new critical path is quite simple: implement software visible special purpose registers which contain current message contents, i.e., r_{V} , r_{IP} and r_{F P}.

On the other hand, special purpose registers presents another optimization for the WOJC code because a ld and join instructions can be made into a single join instruction by utilizing special registers. This new join instruction loads a join counter to a special register r_{CT R} and do ordinal join operation.

The codes are shown in Fig. 10 (a) and (b). Many instructions which were devoted to transfer message contents disappear from these codes, and both decreases by 1 cycle.

3.4 Sequencer Modification

For the WOJC code, further cycle reduction is impossible because the critical path, join-st chain, cannot be made shorten unless a join cache is used. On the other hand, the WJC code can be made into 1 cycle if modification of sequencer is allowed so that we can combine join and jmp instructions into a single join instruction. It should be noted that this combination was made possible by adopting message pipelining scheme. Otherwise, join instruction should decide where to jump based on a counter value, which is difficult to do in 1 cycle.

In this new join instruction, PC must be updated to the content of r_{IP} not to PC+4 in the instruction fetch (IF) cycle. It means some decoding is required in IF cycle to know whether the instruction is join or not.

The resulting code is shown in Fig. 11. Needles to say, further cycle reduction is impossible unless fully hardware managed join mechanism is adopted.

4 Discussion

Fig. 12 shows the summary of code length for each alternative. Join units shown in upper half of this table can be implemented as an SFU of MC88110, though those in lower half cannot be.

Though it is quite difficult to decide which method to choose unless knowing overall performance effect of join operation, several conclusions can be derived from this table. First, as far as concerning easiness of implementation, message pipelining scheme used without join cache seems to be most promising, because hardware & design cost for join cache is too much for reducing cycles from 4 to 3. Secondly, in the case performance is a first priority and the join operation strongly affects total performance, it is reasonable to combine all ideas presented in this report to obtain 1 cycle join operation.

4.1 Join Unit 1: Message Pipelining without Join Cache

Fig. 13 shows the hardware image of this join unit. This hardware is very simple because it doesn’t make decision on control flow. A message buffer to store recirculated message is required in addition to one for incoming messages from a network. Important design issue here is the size of this message buffer. It should be designed so that overflow hardly occurs.

As pointed in Section 3.2, message pipelining affects latency of join operations because the number of messages is increased by 1. However, the fact that code sequence reduces from 6 cycles to 4 cycles would mask this bad effect. For example, consider 4-way join case. Dynamic steps required to handle this join operation is 6*4 for the ordinal join operation versus 4*5 for the message pipelined join operation. Simulation based on some stochastic model should be performed to know accurate performance comparison.

4.2 Join Unit 2: Fully loaded

Fig. 14 shows the hardware image of the join unit which realizes 1 cycle join operation. There are special registers to store contents of a next message {r_{nX}} and a current message {r_{X}}. r_{X}’s are connected to source buses so that they can be directly read into other units. IF stage of sequencer is significantly modified in order to update PC either to PC+4 or IP of a next message depending on an instruction fetched. This modification seems to be inappropriate because instruction decoding is required in IF stage. However, thanks to the message pipelining, this decoding is so simple that it won’t affect the critical path so much (provided that encoding of instructions is such that join can be easily distinguished from other instructions).

However, as mentioned above, special registers and sequencer modification violates SFU requirements described in Section 2.1, which means it totally affects overall processor design. For example, special registers introduce additional state to the processor which should be stored/reloaded in case of exception. About sequencer modification, it is by no means easy to fit above idea into complicated superscalar processor sequencer, which has several PCs for prefetching, speculative issuing, and so on.

From architectural point of view, this processor organization is quite interesting, because it is an direct hybridization of von Neumann and dataflow architectures. In von Neumann architecture, PC is always incremented to give next PC in the IF stage no matter what the instruction is. On the other hand, in dataflow architecture, PC is always carried by a token. Obviously, the processor architecture described in this section hybridizes these two architectures at instruction fetch scheduling level. This processor organization is very close to Iannucci’s hybrid architecture [3].

5 summary

In this report, several alternatives for the join unit are presented, out of which two organizations are selected based on either hardware cost or performance point of view. The first join unit, which performs join operation in 4 cycles, has very simple hardware and fits well into MC88110 SFU. It would be most promising for the first version of *T implementation, though further simulation is required to quantify the performance gain of message pipelining scheme. The second one can execute join operation in 1 cycle but doesn’t fit into MC88110 SFU. Since implementation of this organization would require redesigning of processor itself, it is not realistic to adopt it for *T. However, considering its performance and its attractive hybrid architecture, it is worth studying how to realize this basic idea in a concrete processor design.

References

[1] Rishiyur S.Nikhil, Gregory M. Papadopoulos and Arvind. *T: a Killer Micro for a Brave New World. CSG Memo 325

[2] Rishiyur S.Nikhil, Gregory M. Papadopoulos and Arvind. *T: A Multithreaded Massively parallel Architecture. CSG Memo 325-1

[3] Robert A. Iannucci. Toward a Dataflow/von Neumann Hybrid Architecture. CSG Memo 275