\documentstyle[12pt]{article}
\input /bk/derek/tex/setup
\input /bk/derek/tex/macros
%\input fig
%\input illustrations

%\def\illustrationfileprefix{/bk/derek/research/ms/pics/}

\title{Architectural Consideration of *T Join\_Unit}
\author{Masato Motomura}
\date {\today}

\begin{document}
\maketitle

\begin{abstract} 

In order to realize rapid switching between threads, hardware support
for join operation, called {\it 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 {\it 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.

\end{abstract}  


%\bibliographystyle{plain}
%\pagestyle{empty}
%\markright{DRAFT: \today}

\newpage
\pagestyle{plain}

%1
\section{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
\cite{*t1}\cite{*t2}.

There will be wide variations to realize *T node processor based on
this idea: from adding an autonomous processor, called synchronization
processor \cite{*t1}\cite{*t2}, 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.

%Please note that the work described in this report is preliminary.
%Complete version of the join\_unit (possibly along with other hardware
%primitives) will be reported elsewhere.

%2
\section{Background}

%2.1	
\subsection{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
\subsection{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: 
\begin{enumerate}
\item Move $V$ and $FP$ of a message into registers, and store $V$ into
memory, 
\item Add $r_{IP}$ and $L_D$ (immediate) to calculate a target
instruction pointer, 
\item Load a counter for the join operation (called join counter),
and branch if it is not 0 (join fail),
\item If the join has succeeded, jump to the target instruction calculated
in step 2,
\item If the join has failed, subtract 1 from the join counter and store it
back to memory, 
\item Move $IP$ of a next message into a register and jump to the
instruction pointed.  
\end{enumerate}
Here, $V$ is a 64b data, $FP$ 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 {\it moderate} (though
it is difficult to judge what is moderate) hardware support.

%2.3
\subsection{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 {\it join\_cache} to store join
counters along with a {\it 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. {\it Join} instruction make the
join\_logic to perform following steps:
\begin{enumerate}
\item Read a join counter specified by $CTR$ from a line register,
\item Calculate a new counter value and a target instruction pointer using
immediate $L_D$,
\item 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_{FP}$, respectively.
\item Store the counter value back to the line register.  
\end{enumerate}
$Next$ instruction, which is implicitly encoded with $mov$
instruction, selects a line of the join\_cache according to a $FP$ 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 {\it 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 {\it join} and {\it 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.

\section{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.

\subsection{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.

\subsection{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 {\it join} and {\it 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 {\it
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 {\it 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 {\it 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 $FP$
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.

\subsection{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_{FP}$.

On the other hand, special purpose registers presents another
optimization for the WOJC code because a {\it ld} and {\it join}
instructions can be made into a single {\it join} instruction by
utilizing special registers.  This new join instruction loads a join
counter to a special register $r_{CTR}$ 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.


\subsection{Sequencer Modification}

For the WOJC code, further cycle reduction is impossible because the
critical path, {\it 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
{\it join} and {\it jmp} instructions into a single {\it join}
instruction. It should be noted that this combination was made
possible by adopting message pipelining scheme. Otherwise, {\it join}
instruction should decide where to jump based on a counter value,
which is difficult to do in 1 cycle.

In this new {\it 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 {\it 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.

\section{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.

\subsection{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.

\subsection{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 {\it 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 \cite{hybrid}.

\section{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.

\newpage
\begin{thebibliography}{99}

\bibitem{*t1} Rishiyur S.Nikhil, Gregory M. Papadopoulos and Arvind. *T: a Killer
Micro for a Brave New World. CSG Memo 325

\bibitem {*t2} Rishiyur S.Nikhil, Gregory M. Papadopoulos and Arvind. *T: A
Multithreaded Massively parallel Architecture. CSG Memo 325-1

\bibitem {hybrid} Robert A. Iannucci. Toward a Dataflow/von Neumann Hybrid Architecture.
CSG Memo 275

\end{thebibliography}


\end{document}
