From 0530bda6b45cd08c51524391b32ade7ace4828aa Mon Sep 17 00:00:00 2001 From: adam Date: Sat, 25 Aug 2007 09:47:34 +0100 Subject: [PATCH] archman updates --- doc/archman.bib | 9 +++ doc/archman.tex | 213 +++++++++++++++++++++++++++++++++++++++++-------------- doc/ports.svg | 78 ++++++++++---------- 3 files changed, 209 insertions(+), 91 deletions(-) create mode 100644 doc/archman.bib diff --git a/doc/archman.bib b/doc/archman.bib new file mode 100644 index 0000000..b0433e1 --- /dev/null +++ b/doc/archman.bib @@ -0,0 +1,9 @@ +\bibitem{ies02} + Sutherland, Ivan, {\it UCB-IES02: Fleet -- A One Instruction Computer }\\ + \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies02-FLEET-A.Once.Instruction.Computer.pdf} +\bibitem{ies14} + Sutherland, Ivan, {\it UCB-IES14: The Fleet Definition}\\ + \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies14-Fleet.Definition.pdf} +\bibitem{ies44} + Sutherland, Ivan, {\it UCB-IES44: The Fleet Definition}\\ + \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies44-Fleet.Definition.pdf} diff --git a/doc/archman.tex b/doc/archman.tex index 5d79cc8..c969280 100644 --- a/doc/archman.tex +++ b/doc/archman.tex @@ -1,63 +1,147 @@ -\documentclass[10pt,oneside]{book} +\documentclass[10pt,oneside]{article} \reversemarginpar \usepackage{palatino} \usepackage{epsfig} +\usepackage{verbatim} \usepackage{parskip} \usepackage{register} \usepackage{bytefield} +\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref} \renewcommand{\ttdefault}{cmtt} -\title{The FleetTwo Architecture Manual} +\title{The FleetTwo Architecture Manual\\{\normalsize A Programmer's View of Fleet}} \begin{document} \maketitle + +\begin{thebibliography}{[GDG01]} +\bibitem[IES02]{ies02} + Sutherland, Ivan, + \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies02-FLEET-A.Once.Instruction.Computer.pdf}{\it UCB-IES02: Fleet -- A One Instruction Computer} +\bibitem[IES14]{ies14} + Sutherland, Ivan, + \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies14-Fleet.Definition.pdf}{\it UCB-IES14: The Fleet Definition} +\bibitem[IES44]{ies44} + Sutherland, Ivan, + \href{http://research.cs.berkeley.edu/class/fleet/docs/people/ivan.e.sutherland/ies44-Fleet.Definition.pdf}{\it UCB-IES44: The Fleet Definition} +\end{thebibliography} + +\vspace{3cm} +\begin{abstract} +This manual attempts to detail all those aspects of Fleet which are +visible to a software programmer or compiler backend. + +This document assumes that the reader is broadly familiar with the +Fleet architecture and the motivation behind it. For a far better +introduction to these topics, the reader is referred to \cite{ies02} +\cite{ies14} and \cite{ies44}. Please bear in mind that many of the +details in these documents have been changed, but they still serve as +the authoritative introduction to the architecture. After reviewing +these introductory papers, the reader is invited to digest this +architecture manual for the latest information on the details +necessary to write software and compilers for Fleet. +\end{abstract} + + \pagebreak -\section*{Glossary} +\section*{Introduction (from \cite{ies02})} + +In \cite{ies02}, Sutherland writes: + +{\it +When computers were new, logic and storage were expensive and wires +were relatively cheap. Early computer designers avoided using logic +wherever possible but were not greatly concerned with communication. +They made design choices consistent with the costs of the day. My +favorite example is the jump instruction. Early designers put jump +instructions at the end of each block of code to avoid the expense of +storing the address of the next block while executing the present one. + +Today's chip fabrication methods invert the older cost balance. In +today's integrated circuits logic and memory are now almost free but +communication costs dominate chip area, energy consumption and delay. +In spite of these changes in the stuff from which we make computers, +vestiges of the past remain in many of today's common microprocessor +designs. For example, jump instructions still appear at the end of +each basic block of code in spite of the need to pre-fetch the next +block while executing this one. It seems better today to store a +pointer to the next block and the length of the current block early in +each block of code. + +Instead of following the path of history, I'd like to listen carefully +to what modern chip structures have to teach about how one might build +a modern computer. I see three major lessons. First, simplicity can +reduce cost. Second, moving data will consume most of the time, +energy and chip area of a modern computer. And third, the low cost of +logic makes concurrency available if we can figure out how to use it. + +\begin{itemize} + +\item {\bf Simplicity}: The Fleet architecture seeks simplicity by treating + all processing devices alike... + +\item {\bf Communication}: The Fleet architecture seeks to control the + cost of communication by putting it under direct programmer + control. Thus Fleet avoids instructions like {\sc ADD} or {\sc STORE} that + include concealed communication to and from a register file... -Port\\ -Inlet\\ -Outlet\\ -Pump\\ -Packet\\ -Data Item\\ -Opcode Port\\ -Bypass\\ +\item {\bf Concurrency}: The Fleet architecture assumes concurrency + nearly everywhere... + +\item {\bf Asynchrony}: This provides enormous flexibility for + implementers to improve the performance or reduce the cost of + the processing devices in a Fleet system. -- Synchronous + implementations both of ships and of the switch fabric are + possible provided they use validity or occupancy bits to achieve + the arbitrary delays required at sources and destinations... + +\end{itemize} +} \pagebreak -\section*{Programmer's View of The Ship-Fabric Interface} +\section*{The Programmer's View of The Ship-Fabric Interface} -The diagram below represents a {\it programmer's} conceptual view of -the interface between ships and the switch fabric. Actual -implementations may differ radically, as long as such differences are -not visible to software programs. +The role of the Fleet switch fabric is to carry {\it packets} from +{\it sources} to {\it destinations}. -%\begin{wrapfigure}{R}{2in} -\epsfig{file=ports,width=6in} -%\end{wrapfigure} +A packet consists of a {\it path} and a {\it payload}. The path is +some string of bits which tells the switch fabric how to route from +the desired source to the desired destination. The distinction +between a {\it path} and a {\it destination} is extremely important! +The payload is either a {\it token} or a {\it data item}. If the +payload is a data item, it includes one machine word of data. -The term {\it port} refers to each interface to the ship (either -inbound or outbound) and the machinery required to manage this -interface. The machinery consists of a {\it latch}, which is as wide -as a single machine word, a {\it pump}, which is a circular fifo of -instruction-width latches, and a number of {\it sources} or {\it - destinations}. Sources and destinations which can only send or -recieve tokens (rather than data items) are drawn as dashed lines. -Buffering fifos are drawn where they appear. +The diagram below represents a {\it programmer's} conceptual view of +the interface between ships and the switch fabric. Actual +implementation circuitry may differ substantially. Sources and +destinations which can send and recieve only tokens -- not data items +-- are drawn as dashed lines. -Note in particular that every pump is a destination capable of -recieving a data word. This is how instructions are dispatched to -pumps -- they are inserted into the switch fabric as {\it packets} -whose destination addresses +\vspace{0.3cm} +\begin{center} +\epsfig{file=ports,width=4in} +\end{center} +\vspace{0.3cm} -Note that addresses are actually paths. +The term {\it port} refers to each interface to the ship, the {\it + valve} connecting it to the switch fabric, and the corresponding +sources and destinations on the switch fabric. -Define packets. +Each valve consists of a {\it data latch}, which is as wide as a +single machine word and a {\it pump}, which is a circular fifo of +instruction-width latches. The contents of the instruction fifo +control the data latch, as future chapters will explain. +Note that the pump in each valve has a destination of its own, and +that there is no buffering fifo guarding this destination. Note that +all other destinations are guarded by a buffering fifo; the size of +this fifo is exposed to the software programmer so she can ensure that +deadlock does not occur. \pagebreak \section*{Data Formats} -\subsection*{Packet Destination Address (12 bits)} +\subsection*{Packet Path (12 bits)} These bits appear physically within the switch fabric, and have ``address bit timing.'' The {\tt T} bit is the ``tokenhood'' bit; if @@ -68,16 +152,14 @@ fabric data latches to fire. \begin{bytefield}{49} \bitheader[b]{37,47,48}\\ \bitbox{1}{T} - \bitbox{11}{Destination Address} + \bitbox{11}{Path} \bitbox[l]{37}{} \end{bytefield} } \subsection*{Data Word In Memory (37 bits)} -A word of memory is 37 bits wide. For convenience, we assume that the -memory word width is also the width of a pointer as well as the width -of all on-chip data item registers. +A word of data is 37 bits wide. {\tt\footnotesize \begin{bytefield}{49} @@ -87,16 +169,13 @@ of all on-chip data item registers. \end{bytefield} } -\subsection*{Data Packet In Flight (49 bits)} - -A {\it data packet} is a data item in the switch fabric, on its way to -some destination. +\subsection*{Packet In Flight (49 bits)} {\tt\footnotesize \begin{bytefield}{49} \bitheader[b]{0,36,37,47,48}\\ \bitbox{1}{T} - \bitbox{11}{Destination Address} + \bitbox{11}{Packet Path} \bitbox{37}{Data Word} \end{bytefield} } @@ -104,13 +183,17 @@ some destination. \subsection*{Instruction In Memory (37 bits)} An instruction must be no wider than a memory word. The next section -explains the bits in greater detail. +explains the bits in greater detail. The {\tt Instruction Path} is +the path which the instruction itself will take in order to arrive at +the desired pump destination. The {\it Data/Token Path} is placed on +any packet inserted into the switch fabric as a result of executing +the instruction. {\tt\tiny \begin{bytefield}{49} \bitheader[b]{0,10,11,17,18-26,36}\\ \bitbox[r]{12}{} - \bitbox{11}{Instruction Register Address} + \bitbox{11}{Instruction Path} \bitbox{1}{K} \bitbox{1}{L} \bitbox{1}{Ti} @@ -120,22 +203,22 @@ explains the bits in greater detail. \bitbox{1}{To} \bitbox{1}{Rq} \bitbox{7}{Count} - \bitbox{11}{Data/Token Destination} + \bitbox{11}{Data/Token Path} \end{bytefield} } \subsection*{Instruction Packet In Flight (49 bits)} -A {\it instruction packet} is an instruction in the instruction horn -(which may or may not be the same thing as the data horn), on its way -to some instruction register (Valve). +Note that Fleet simply copies the {\tt Instruction Path} field, bit +for bit, into the packet {\tt Path} field in order to ``dispatch'' an +instruction. {\tt\tiny \begin{bytefield}{49} \bitheader[b]{0,10,11,17,18-25,37,47,48}\\ \bitbox[r]{1}{0} - \bitbox{11}{Instruction Register Address} - \bitbox[lr]{11}{} + \bitbox{11}{Instruction Path} + \bitbox{11}{Instruction Path} \bitbox{1}{K} \bitbox{1}{L} \bitbox{1}{Ti} @@ -145,7 +228,7 @@ to some instruction register (Valve). \bitbox{1}{To} \bitbox{1}{Rq} \bitbox{7}{Count} - \bitbox{11}{Data/Token Destination} + \bitbox{11}{Data/Token Path} \end{bytefield} } @@ -321,7 +404,31 @@ Note how a ``standing'' instruction is encoded as {\tt Count=1111111} \end{itemize} \pagebreak -\section{Future Directions} +\section*{Fleet Assembly Language} + +The Fleet Assembly language is designed to be a human-readable +depiction of the bits which comprise a Fleet program. The formal +syntax is given below: + +\verbatiminput{fleet.g} + +\pagebreak +\section*{Java APIs} +\subsection*{Representing Code} +\subsection*{Representing Ships} + +\pagebreak +\section*{Misc} + +\begin{verbatim} +- sequencing guarantees +- codebag format +- behavior when token arrives at data port, vice versa +- overlapping codebags +\end{verbatim} + +\pagebreak +\section*{Future Directions} Looking back on the design of the pump, several things are now apparent which were not initially. In particular, it seems that it diff --git a/doc/ports.svg b/doc/ports.svg index bc2ab2d..a52652e 100644 --- a/doc/ports.svg +++ b/doc/ports.svg @@ -71,7 +71,7 @@ inkscape:pageshadow="2" inkscape:zoom="1.5855365" inkscape:cx="510.02639" - inkscape:cy="102.56622" + inkscape:cy="356.19542" inkscape:document-units="px" inkscape:current-layer="layer1" showgrid="true" @@ -110,7 +110,7 @@ sodipodi:nodetypes="cccc" /> + d="M 347.24409,496.06299 L 484.97638,496.06299" + id="path3195" + sodipodi:nodetypes="cc" /> + d="M 450.45669,177.16535 L 357.41732,177.16535" + id="path3193" + sodipodi:nodetypes="cc" /> Ship Pump Destination + style="font-size:18px;text-align:center;text-anchor:middle;fill:#800080">Destination Destination + style="font-size:18px;text-align:center;text-anchor:middle;fill:#800080">Destination Source + style="font-size:18px;text-align:center;text-anchor:middle;fill:#008080">Source Source + style="font-size:18px;text-align:center;text-anchor:middle;fill:#008080">Source Destination + style="font-size:18px;fill:#800080">Destination Destination + style="font-size:18px;text-align:center;text-anchor:middle;fill:#800080">Destination