cf2a404eba18e11585bbfd07d830435ec47ae3bc
[mw/milkymist.git] / doc / thesis.tex
1 % http://www.idt.mdh.se/phd/thesis/kthesis-1.0/
2 % TODO: spellcheck
3 \documentclass[a4paper,11pt]{kthesis}
4 \usepackage[T1]{fontenc}
5 \usepackage[normalem]{ulem}
6 \usepackage[english]{babel}
7 \usepackage{boxedminipage}
8 \usepackage{graphicx}
9 \usepackage{moreverb}
10 \usepackage{float}
11 \usepackage{cite}
12 \usepackage{tabularx}
13 \usepackage{units}
14 \usepackage{amsmath}
15 \usepackage{wasysym}
16
17 \title{A performance-driven SoC architecture for video synthesis}
18 \date{June 2010}
19 \type{Master of Science Thesis in System-on-Chip Design}
20 \department{Department of Software and Computer Systems}
21 \author{S\'ebastien Bourdeauducq}
22 \imprint{Stockholm 2010}
23 \publisher{KTH}
24 \tmnotice{Milkymist is a trademark of S\'ebastien Bourdeauducq.}
25 \trita{xxx-nnnn}
26 \issn{nnnn-nnnn}
27 \isrn{KTH/xxx/R-{}-nn/n-{}-SE}
28 \isbn{x-xxxx-xxx-x}
29 \begin{document}
30 \begin{abstract}
31 TODO
32 \end{abstract}
33
34 \begin{acknowledgments}
35 First, I would like to express my gratitude to Professor Mats Brorsson, my supervisor and examiner at the Royal Institute of Technology, for having the open-mindedness of letting me write my thesis on this subject and his help and advice with it.
36
37 Then, I would like to thank all the researchers who have retained their copyright on their papers (or have put them in the public domain) and distribute them online for everybody to download freely (incidentally in accordance with the principle of free exchange of information from the KTH ethics policy). This in spite of the default agreement of many publishers such as the IEEE, which asks authors to assign their copyrights to the publishers so the latter have the exclusive permission to sell the download of documents that they did not write, without giving back to the authors, at a price supposedly meant to cover publishing expenses but which is not justified by today's low costs of network bandwidth and servers.
38
39 Thanks to these researchers, I have been able to access quality scientific literature before I went to a university, from which I have learned a lot. Even throughout the writing of this Master's thesis, papers freely available online enabled greater productivity as access to them was much faster.
40
41 Thanks also go to Lattice Semiconductor for opening the source code of their LatticeMico32 processor core.
42
43 Finally, special thanks go to all the people who are indirectly involved with this Master's thesis project: Henry de Beauchesne (Xilinx) for getting me started with high-end FPGA tools, Shawn Tan (Aeste Works (M) Sdn Bhd) for his help with understanding the WISHBONE bus, Gregory Taylor (NASA's Jet Propulsion Laboratory) for letting me know that they were using parts of my code in the development of a communications system to be put onboard the international space station, Takeshi Matsuya (Keio University) for his work on the port of Linux to the system-on-chip described herein, Michael Walle for developing support of the system-on-chip in the QEMU emulator and Wolfgang Spraul (Sharism at Work Ltd.) for proposing me an agreement for manufacturing devices using the system-on-chip design.
44 \end{acknowledgments}
45
46 \tableofcontents
47 \listoffigures
48 \listoftables
49
50 \mainmatter
51
52 \chapter{Introduction}
53 The open source model supports the idea that any individual, if he or she has the required level of technical knowledge, can realistically use, share and modify the design of a technical system. During the nineties, this development model gained popularity in the software world with, most notably, the Linux operating system. But it was not viable for complex SoCs until a few years ago, because the cost of prototyping semiconductor chips is prohibitive and field programmable gate arrays (FPGAs) used to be too slow, too small, and too expensive. System-on-chip design and hands-on computer architecture therefore remained a field reserved to well-funded academia and research and development laboratories of companies of a significant size and wealth, who had access to large FPGA clusters or even semiconductor foundries.
54
55 \begin{figure}[htp]
56 \centering
57 \includegraphics[height=95mm]{ikosboards.eps}
58 \caption{FPGA boards of the Ikos Pegasus ASIC emulator (ca. 1999).}
59 \label{fig:ikos}
60 \end{figure}
61
62 But the cost of FPGAs is falling (this was already the case between 1985 and 1994~\cite{fpgacost} and the trend has continued since then) and relatively fast and high-density devices are today becoming available to the general public. For an example of this falling cost (and increasing densities and speed), we will mention the Ikos Pegasus application specific integrated circuit (ASIC) emulator, whose insides are depicted in figure~\ref{fig:ikos}. The LatticeMico32 CPU core used in the system-on-chip described in this thesis occupies alone 60\% of the resources of one of the XC4036XL FPGAs of this device, and runs at 30MHz. The Ikos Pegasus was a state-of-the-art device a decade ago. It consumes up to 3 kilowatts of power, weights dozens of kilos and probably costed the equivalent of several millions of SEK. The same CPU core now occupies about 15\% of a modern FPGA costing less than 500 SEK, where it runs in excess of 100MHz.
63
64 \begin{figure}
65 \centering
66 \includegraphics[height=55mm]{newlogo.eps}
67 \caption{Project logo.} \label{fig:projectlogo}
68 \end{figure}
69
70 This evolution makes it possible to implement complex high-performance system-on-chips (SoC) that can be modified and improved by anyone, thanks to the flexibility of the FPGA platform.
71
72 This Master's thesis introduces Milkymist\texttrademark \cite{milkymist}, a fast and resource-efficient FPGA-based system-on-chip designed for the application of rendering live video effects during performances such as concerts, clubs or contemporary art installations. Such effects are already popularized by artists known as ``video jockeys'', or ``VJs''. VJing is commonly done with a PC and computer software such as GrandVJ~\cite{grandvj} or Resolume~\cite{resolume}. However, this approach has some drawbacks and using an embedded device instead would be interesting:
73 \begin{itemize}
74 \item A device of very small size and weight is possible, which is convenient in mobile or temporary setups.
75 \item Boot and set-up time (launching the software) can be greatly reduced (to a few seconds).
76 \item Many interfaces for interactive performances (MIDI, DMX, video input, low-level digital I/O for user sensors) can be integrated. By comparison, the equivalent PC-based solution would be expensive and bulky.
77 \end{itemize}
78
79 Besides the fact that this is an interesting, creative and popular application, it is also demanding in terms of computational power and memory performance. Such a project would also be a proof that high performance open source system-on-chip design is possible in practice; with a view to help, foster and catalyze similar ``open hardware'' initiatives. As the Milkymist system-on-chip is entirely made of synthesizable Verilog and, for the most part, released under the GNU General Public License (GPL), its code can be re-used by other open hardware projects.
80
81 Meeting the performance constraints while still using cheap and relatively small FPGAs is perhaps the most interesting and challenging technical point of this project, and it could not be done without substantial work in the field of computer architecture. This is what this Master's thesis covers.
82
83 \chapter{Background}
84 \section{Video synthesis}
85 \subsection{Overview}
86 MilkDrop~\cite{milkdrop} (figure~\ref{fig:milkdrop}) is a popular open source video synthesis framework that was originally made to develop visualization plugins for the Winamp audio player. People have since then ported MilkDrop to many different platforms~\cite{wpmilkdrop} and made it react to live events, such as captured audio and video~\cite{visikord} (figure~\ref{fig:visikord}) or movements of a Wiimote remote control~\cite{wiimodemd}.
87
88 The idea behind the Milkymist project is to implement an embedded video synthesis platform on a custom open source system-on-chip, that is based on the same rendering principle of MilkDrop but with more control interfaces and features. The device built around the system-on-chip should be stand-alone, which means that a graphical user interface for configuring the visual effects should be implemented (figure~\ref{fig:flickernoise}).
89
90 \begin{figure}[htp]
91 \centering
92 \includegraphics[height=65mm]{milkdrop2.eps}
93 \caption{Sample video frame from the MilkDrop visual synthesizer.}
94 \label{fig:milkdrop}
95 \end{figure}
96
97 \begin{figure}[htp]
98 \centering
99 \includegraphics[height=60mm]{visikord.eps}
100 \caption{Sample video frame from Visikord, a program mixing live video into MilkDrop.}
101 \label{fig:visikord}
102 \end{figure}
103
104 \begin{figure}[htp]
105 \centering
106 \includegraphics[height=85mm]{flickernoise.eps}
107 \caption{The embedded user interface (based on Genode FX~\cite{genodefx}) of Flickernoise, the Milkymist VJ application. The patch editor is shown, with per-frame and per-vertex equations.}
108 \label{fig:flickernoise}
109 \end{figure}
110
111 \subsection{Principle}
112 \label{subsec:mdprinciple}
113 \subsubsection{General mode of operation}
114 The MilkDrop-like renderer is the most compute and memory intensive process, from which stem most of the technical challenges. We will now get into more details about how the renderer works (figure~\ref{fig:renderflow}).
115
116 \begin{figure}[htp]
117 \centering
118 \includegraphics[height=130mm]{renderflow.eps}
119 \caption{Basic MilkDrop rendering flow.}
120 \label{fig:renderflow}
121 \end{figure}
122
123 Rendering is based on a frame buffer on which the steps below are continuously repeated. This repetition is at the origin of many feedback or ``fractal'' effects.
124 \begin{itemize}
125 \item The current frame is distorted (zoomed, translated, warped, scaled, rotated...) by texture mapping. This step is described with more detail in section~\ref{sec:tm}.
126 \item The frame is darkened (the colors are shifted to black).
127 \item A waveform of the currently played music is drawn. The wave can be drawn linearly (like an oscilloscope), in a circle, etc.
128 \item Borders around the screen are drawn. If the distortion zooms out, the borders will be pulled into the picture (some effects are based on this).
129 \item \textit{Motion vectors} are drawn. Motion vectors are simply a grid of dots, which can be used to generate effects by playing with the distortion.
130 \item The process repeats from the beginning.
131 \end{itemize}
132
133 These are the basic features of MilkDrop. There are more (custom waves, shapes,...) which are listed on the MilkDrop website~\cite{milkdrop}. Some other features (such as adding live video) will be added to the Milkymist renderer in the future.
134
135 This process is done on an internal frame buffer whose horizontal and vertical dimensions are a power of 2. This frame buffer is then scaled to the size of the screen in order to be displayed. This brings two features:
136 \begin{itemize}
137 \item The sizes being a power of 2 allows out-of-bounds texture coordinates to be wrapped (in order to repeat the texture) by simply performing a bitwise AND of the coordinate, instead of the full computation of a division remainder which is a much more expensive operation (even on the traditional GPUs MilkDrop was designed for).
138 \item It enables the implementation of the \textit{video echo} effect: after the internal frame buffer has been drawn to the screen at its nominal dimensions, a zoomed and semi-transparent copy of it can be overprinted.
139 \end{itemize}
140 It must be noted that this two-step process increases the computation time and the consumption of memory bandwidth.
141
142 All the steps of the rendering are heavily parametrizable by the user, using a coded format called a \textit{patch} or \textit{preset} which defines the aspect and the interaction forms of a particular visual effect. The listing of a sample patch is given by figure~\ref{fig:samplepatch} and the meaning of the language is explained below.
143
144 \begin{figure}
145 \centering
146 \begin{boxedminipage}{13cm}
147 \begin{verbatim}
148 fDecay=0.980000
149 nWaveMode=2
150 bTexWrap=1
151 bMotionVectorsOn=0
152 zoom=1.046000
153 rot=0.020000
154 cx=0.500000
155 cy=0.500000
156 warp=0.969000
157 sx=1.000000
158 sy=1.000000
159 wave_r=0.600000
160 wave_g=0.600000
161 wave_b=0.600000
162 wave_x=0.500000
163 wave_y=0.470000
164 per_frame_1=wave_r = wave_r + 0.400*( 0.60*sin(0.933*time)
165   + 0.40*sin(1.045*time) );
166 per_frame_2=wave_g = wave_g + 0.400*( 0.60*sin(0.900*time)
167   + 0.40*sin(0.956*time) );
168 per_frame_3=wave_b = wave_b + 0.400*( 0.60*sin(0.910*time)
169   + 0.40*sin(0.920*time) );
170 per_frame_4=zoom = zoom + 0.010*( 0.60*sin(0.339*time)
171   + 0.40*sin(0.276*time) );
172 per_frame_5=rot = rot + 0.050*( 0.60*sin(0.381*time)
173   + 0.40*sin(0.579*time) );
174 per_frame_6=cx = cx + 0.030*( 0.60*sin(0.374*time)
175   + 0.40*sin(0.294*time) );
176 per_frame_7=cy = cy + 0.030*( 0.60*sin(0.393*time)
177   + 0.40*sin(0.223*time) );
178 per_vertex_1=sx=sx-0.04*sin((y*2-1)*6+(x*2-1)*7+time*1.59);
179 per_vertex_2=sy=sy-0.04*sin((x*2-1)*8-(y*2-1)*5+time*1.43);
180 \end{verbatim}
181 \end{boxedminipage}
182 \caption{Excerpt from the MilkDrop preset ``Geiss -- Warp of Dali 1'' (with some simplifications).}
183 \label{fig:samplepatch}
184 \end{figure}
185
186 \subsubsection{Initial conditions}
187 The patch begins with a series of parameters which are used to initialize the renderer, and many of them are kept constant during the execution of the patch. For example:
188 \begin{itemize}
189 \item \verb!bMotionVectorsOn=0! turns off the drawing of the motion vectors.
190 \item \verb!nWaveMode=2! selects one of the many ways of drawing the audio waveform.
191 \item \verb!sx=1.000000! and \verb!sy=1.000000! set the X and Y scaling factors of the distortion to 1 (i.e. the frame is initially not scaled).
192 \item \verb!wave_r=0.600000!, \verb!wave_g=0.600000! and \verb!wave_b=0.600000! set the initial RGB color with which the wave is drawn (it is initially grey).
193 \end{itemize}
194
195 \subsubsection{Per-frame equations}
196 Using initial conditions only limits the interaction and evolution possibilities of the patch.
197
198 It is therefore possible to make the parameters evolve over time, thanks to the per-frame equations. As their name suggests, the per-frame equations are mathematical expressions that are evaluated at each frame.
199
200 The example patch (figure~\ref{fig:samplepatch}) shows some of them (the lines beginning with \verb!per_frame!). In this example, they change the wave color over time by modifying the \verb!wave_r!, \verb!wave_g! and \verb!wave_b! values in sinusoidal patterns, as well as the zoom (\verb!zoom!), rotation (\verb!rot!) and center of rotation (\verb!cx! and \verb!cy!).
201
202 Per-frame equations can make the patch react to sound, for example through the \verb!bass!, \verb!mid! and \verb!treb! variables that indicate the intensity of the sound in three frequency bands. One of the ideas in Milkymist is to add other variables that can be controlled by the DMX512 and MIDI protocols, enabling the use of a whole range of devices commonly found among musicians (electronic instruments, faders, stage light consoles, joysticks,...) to control the visual effects.
203
204 \subsubsection{Per-vertex equations}
205 Per-vertex equations are used to fine-tune the distortion applied to the picture.
206
207 Indeed, as explained further in section~\ref{sec:tm}, the distortion works by using a mesh of control points (vertices) that can be moved to transform the image in many different ways (effects such as zooming, scaling and rotating are implemented by moving the vertices).
208
209 Per-vertex equations are thus evaluated at each vertex (whose position can be retrieved through the \verb!x! and \verb!y! variables), and alter the position of that vertex. In the example patch (figure~\ref{fig:samplepatch}), the image is locally scaled horizontally and vertically by factors depending on the position of the vertex and on the time, resulting in a twisted visual effect.
210
211 As discussed in chapter~\ref{ch:tmu}, the floating point computations for each vertex are intensive and required the use of a dedicated coprocessor.
212
213 \section{Open source SoC platforms}
214 There is an existing effort to build open source system-on-chips. It is interesting to review these projects in order to look forward to building upon them --- possibly adding hardware accelerators or performing other modifications in order to improve performance.
215
216 There are many SoC designs available on the Internet, which are more or less mature. The system-on-chip projects listed here meet the following criteria:
217 \begin{itemize}
218 \item they have been shown to work on at least one FPGA board
219 \item they are released under an open source license
220 \item they comprise a synthesizable RISC CPU
221 \item the CPU is supported by a C and C++ compiler
222 \item they include a RS232 compatible UART (for a debug console)
223 \item they support interfacing to off-chip SDRAM memory
224 \end{itemize}
225
226 \subsubsection{OpenSPARC}
227 OpenSPARC~\cite{opensparc} is the well-known SPARC processor of Sun Microsystems which is now released under an open source license and included into a SoC FPGA project.
228
229 Implemented on a FPGA, this processor is extremely resource-intensive. A cut-down version of the CPU core only, called the ``Simply RISC S1'', occupies at least 37000 FPGA look-up tables (LUT) without the caches~\cite{simplyrisc}. This is about twice the logic capacity of the Virtex-4 XC4VLX25 FPGA.
230
231 As it turns out, the OpenSPARC architecture is a very complex design which implements a huge number of techniques which increase the software execution speed (instructions per clock cycle). While this is a wise choice for a software-centric processor implemented on a fully custom semiconductor chip, with a FPGA process it is more appealing to keep the software processor simple in order to save resources and make room for custom hardware accelerators, taking advantage of the FPGA flexibility.
232
233 \subsubsection{GRLIB}
234 GRLIB~\cite{grlib} is a very professional and standard-compliant library of SoC cores. The library features a comprehensive set of cores: AMBA AHB/APB bus control elements, the LEON3 SPARC processor, a 32-bit PC133 SDRAM controller, a 32-bit PCI bridge with DMA, a 10/100/1000 Mbit Ethernet MAC,  16/32/64-bit DDR SDRAM/DDR2 SDRAM controllers and more.
235
236 However, its drawbacks are:
237 \begin{itemize}
238 \item Code complexity. GRLIB is written in VHDL and makes intensive use of custom types, packages, generate statements, etc.
239 \item Cores are not self-contained. GRLIB defines many ``building blocks'' that are used everywhere else in the code, making it difficult to re-use code in another project which is not based on GRLIB.
240 \item Significant FPGA resource usage. A system comprising the LEON3 SPARC processor with a 2-way set-associative 16kB cache and no memory management unit (MMU), the DDR SDRAM controller, a RS232 serial port, and an Ethernet 10/100 MAC uses 13264 FPGA look-up tables (LUT). They map to 79\% of the Virtex-4 XC4VLX25 FPGA. We have carried out the test with the Xst synthesizer, Xilinx ISE 11.3, and GRLIB 1.0.21-b3957 (GPL release) using the default provided synthesis scripts. This undermines the possibility of adding hardware acceleration cores. In~\cite{softcorecomp}, a significant resource usage was also reported for an older version of LEON.
241 \item Relatively low clock frequency. With the same parameters as above, the maximum clock frequency is 84MHz.
242 \end{itemize}
243
244 Because of these reasons, GRLIB was not retained.
245
246 \subsubsection{ORPSoC (OpenRISC)}
247 ORPSoC is based on the OpenRISC~\cite{openrisc} processor core, which is the flagship product of OpenCores, a community of developers of open source system-on-chips. ORPSoC is essentially maintained by ORSoC AB.
248
249 ORPSoC notably features the OpenRISC OR1200 processor core, the Wishbone~\cite{wishbone} bus, comprehensive debugging facilities, a 16550-compatible RS232 UART, a 10/100Mbps Ethernet MAC and a SDRAM controller.
250
251 Unfortunately, ORPSoC is resource-inefficient and buggy. The OpenRISC implementation is not well optimized for synthesis. We carried out tests on the August 17, 2009 OpenRISC release. Still using the XC4VLX25 FPGA as target, synthesis with Xst and Xilinx ISE 11.4 yields an utilization of 5077 LUTs for the CPU core only (using the default FPGA configuration: no caches, no MMU, multiplier, and with the implementation of the RAMs using the RAMB16 elements of the FPGA selected), running at approximately 100MHz. A similar resource usage is reported in~\cite{softcorecomp}. The synthesis report shows asynchronous control signals where there should not be (such as on the output of the program counter), which can be an indication of poor quality of the design. Other IP cores comprising ORPSoC have similar issues (we tested the 16550 UART and the Ethernet MAC). Finally, the provided SDRAM controller only supports the low-bandwidth 16-bit single data rate option, has a high latency due to the extensive use of clock domain transfer FIFOs, does not support pipelined transfers and has a poorly written code.
252
253 OpenRISC and ORPSoC therefore do not seem to be a good platform for the performance-demanding and resource-constrained video synthesis application.
254
255 \subsubsection{LatticeMico32 System}
256 This product~\cite{mico32} from the FPGA vendor Lattice Semiconductor is comparable to Microblaze~\cite{microblaze} and Nios II~\cite{nios} from its competitors, respectively Xilinx and Altera.
257
258 Like its competing products, LatticeMico32 System features a broad library of light, fast and FPGA-optimized SoC cores.
259
260 One interesting move made by Lattice Semiconductor is that parts of the LatticeMico32 System are released under an open source license, and most notably the custom LatticeMico32 microprocessor core. LatticeMico32 System is also based upon the Wishbone~\cite{wishbone} bus, whose specification is free of charge and freely distributable.
261
262 While it is perhaps technically possible to build Milkymist on top of the LatticeMico32 System, there are licensing issues concerning most notably the DDR SDRAM controller which is proprietary.
263
264 However, the LatticeMico32 microprocessor core is interesting. Synthesized for the XC4VLX25 with the 2-way set-associative caches, the barrel shifter, the hardware divider and the hardware multiplier enabled, it occupies only about 2400 4-LUTs and runs at more than 100MHz.
265
266 This microprocessor core has been retained for use in Milkymist, as described in chapter~\ref{ch:sw}.
267
268 \subsubsection{Microblaze and Nios II}
269 Even though we are not interested in proprietary designs, we still give a brief overview of the resource usage of Microblaze and Nios II systems as a comparison.
270
271 \paragraph{Microblaze.} In~\cite{softcorecomp}, the Microblaze core is reported to use approximately 2400 LUTs, like LatticeMico32. The platform builder GUI in Xilinx ISE 12.1 also limits the frequency of Microblaze systems to 100MHz when targetting the Virtex-4 family. Thus, Microblaze is close to LatticeMico32 regarding area and frequency.
272
273 \paragraph{Nios II.} According to an Altera report~\cite{niosbench}, Nios II/f uses 1600 Cyclone II LEs. A LE is mainly comprised of a 4-LUT and a register, which is comparable to the Virtex-4 architecture on which LatticeMico32 was tested. Thus, it seems that the Nios II core would be approximately two thirds of the area of LatticeMico32.
274
275 Some differences can be noted between the LatticeMico32 configuration and the Nios II/f configuration used in the Altera report:
276 \begin{itemize}
277 \item Caches are direct-mapped and 512 bytes (each).
278 \item There is no multiplier.
279 \item Nios II/f uses a dynamic branch predictor, while LatticeMico32 uses a static branch predictor.
280 \item The report does not say if the optional hardware divider, multiplier and shifter (that were enabled in LatticeMico32) were selected.
281 \end{itemize}
282
283 The Nios II is also reported to run at 140 MHz with this configuration and UART, JTAG UART, SDR SDRAM controller and timer peripherals. This is very fast, but cannot be compared to the LatticeMico32 results on Virtex-4 for two reasons:
284 \begin{itemize}
285 \item Routing resources and logic delays for the two FPGA families are different.
286 \item It is possible that Altera hand-tuned the Nios II processor to their FPGA technology.
287 \end{itemize}
288
289 \section{DRAM technology}
290 DRAM is by far today's dominant memory technology, often being the only affordable solution when relatively large densities (typically more than a few megabytes) are required. Unfortunately, DRAMs are not straightforward devices and we need preliminary knowledge specific to this technology in order to understand the choices discussed in chapter~\ref{ch:memory}. Indeed, in order to reduce system costs, the intelligence has been moved away from the memory chips and into the memory controller~\cite{dramlowcost}, leaving the controller designer with the task of dealing with the low-level details of the DRAM technology.
291
292 We will therefore explain how the SDRAM (synchronous DRAM) technology works. These principles are the same for the original single data rate (SDR) SDRAM, and for the subsequent double data rate DDR, DDR2 and DDR3 memories. In all that follows, we suppose that the logic level 0 is represented by a voltage of 0 volts, and a logic level 1 is represented by a positive voltage H.
293
294 A DRAM memory bank (figure~\ref{fig:drambank}) is organized as a two dimensional array of cells. Each cell is comprised of a transistor connected to a capacitor. A cell stores one bit of information, indicated by the presence or not of a charge in the capacitor. The transistor acts as a switch that connects the capacitor to the \textit{bit line} (vertical lines) when the \textit{word line} (horizontal lines) its gate is connected to carries a high logic level.
295
296 A decoder translates the row address presented to the DRAM device and activates one of the word lines, according to the address.
297
298 Each bit line is connected to a \textit{sense amplifier}, which is a positive feedback device that, when switched on, turns any voltage X on the bit line between 0 and H into 0 (if $X < \frac{H}{2}$) or H (if $X > \frac{H}{2}$). The set of sense amplifiers is called the \textit{page buffer}.
299
300 \begin{figure}
301 \centering
302 \includegraphics[height=100mm]{drambank.eps}
303 \caption{Block diagram of a DRAM memory bank.}
304 \label{fig:drambank}
305 \end{figure}
306
307 Accesses to a SDRAM bank are made as follows:
308 \begin{enumerate}
309 \item We assume the SDRAM is in the \textit{precharged} (idle) state. In this state, no word line is active, the sense amplifiers are turned off and all the bit lines are held at a voltage of $\frac{H}{2}$.
310 \item The SDRAM controller presents the row address and issues an ACTIVATE command. In response to this command, the SDRAM device enables the row decoder and one of the word lines is asserted. This has the effect of connecting all the capacitors of the DRAM cells in the row to their respective bit lines. A transfer of electric charge occurs between the ``parasitic'' capacitors of the word lines (which were charged at a voltage of $\frac{H}{2}$) and the DRAM cell capacitors, which were either discharged (at 0 volts) or charged at a voltage of H. This causes a small change $\epsilon$ in the potential of the bit line, which becomes $\frac{H}{2}-\epsilon$ or $\frac{H}{2}+\epsilon$ (depending on the charge initially stored in the DRAM cell capacitor). Then, the SDRAM device turns on all the sense amplifiers of the bank. On each bit line, the positive feedback takes over and amplifies the voltage difference $\epsilon$ until the level of the bit line reaches 0 or H. The ACTIVATE command is now completed and the row is said to be \textit{opened}. The DDR SDRAM chips used in the project (on the Xilinx ML401 board) take $20\unit{ns}$ to complete these operations.
311 \item Once a row has been opened, the controller can present the column address and issue READ and WRITE commands to transfer data. Reading is done by simply measuring the voltages on the bit lines, and writing can be achieved by forcing the bit lines to a particular level. There is a delay, called the CAS\footnote{CAS stands for Column Address Strobe, which is the name of the DRAM chip pin that the controller asserts at this stage.} latency, between a READ command being sent and the data being returned by the device. This delay is of $20\unit{ns}$ with the chips used in the project. However, read operations are pipelined, which means that a new READ command can be sent while the previous one is still transferring data. With proper scheduling, a full utilization of the available I/O bandwidth can be achieved.
312 \item Before accessing another row, the memory controller must disconnect the opened row from the bit lines and go back into the precharged state. It does so by issuing a PRECHARGE command to the device. The device takes some time to process the command (during which the bank cannot be accessed), which is $20\unit{ns}$ with the chips used in the project.
313 \end{enumerate}
314
315 From this principle of operation, it becomes apparent that a performance-oriented controller should try to make several transfers in the same row before opening another one, in order to reduce the time wasted to switching rows.
316
317 \subsection{Multiple banks}
318 SDRAM memory chips contain multiple DRAM banks internally, which share the I/O, command and address pins. Additional bank address pins select the bank to send commands to.
319
320 Having multiple banks brings two advantages:
321 \begin{itemize}
322 \item Being able to execute several commands simultaneously (assuming there is no resource conflict for the pins). For example, one bank can be activating one row while another bank is transferring data.
323 \item Having several rows open (one per bank), which can reduce the number of required row switches and thus improve performance.
324 \end{itemize}
325
326 The controller is responsible for managing the banks, and mapping absolute memory addresses to particular banks. Appropriate bank mapping can improve performance~\cite{pagemode}.
327
328 Standard DDR SDRAM chips come with four internal banks.
329
330 \subsection{Refreshing}
331 Because the DRAM capacitors are not perfect, they gradually lose their charge over time, which results in data corruption.
332
333 The solution is to periodically recharge the capacitors, which is done by opening the rows one by one. SDRAM chips provide an AUTO REFRESH command which opens and closes one row in all banks (and increments an internal counter so that the next AUTO REFRESH command will target another row), but it is the responsibility of the controller to issue it. Furthermore, the controller must precharge all banks before a refresh.
334
335 With the memory chips used in the project, a refresh must be made every $7.8\unit{\mu s}$ and takes in the worst case $20+80+4 \cdot 20=180\unit{ns}$ (precharge time\footnote{All banks can be precharged at the same time with a single command.} + refresh time + activation time for each bank), so it has a small impact on the memory bandwidth (about 2\%).
336
337 \section{Texture mapping}
338 \label{sec:tm}
339 Texture mapping is a common computer graphics operation found in accelerated 3D APIs like OpenGL and DirectX. It is typically used to draw textured 3D polygons on the screen. It can also distort an image (see figure~\ref{fig:distorted} for an example), and MilkDrop uses it for this purpose.
340
341 \begin{figure}
342 \centering
343 \includegraphics[height=70mm]{tesselsanofi.eps}
344 \caption{Example of distorted picture.}
345 \label{fig:distorted}
346 \end{figure}
347
348 With common GPUs, texture mapping is performed on triangles (and more complex polygons are broke down into a series of triangles). The inputs to the algorithm are the 2D (possibly projected from the original 3D coordinates) positions of the three vertices of the triangle to be filled, and the 2D texture coordinates for these three vertices.
349
350 The algorithm then draws a textured triangle pixel by pixel, by interpolating linearly the texture coordinates of the vertices for each pixel and then copying the texture pixel (\textit{texel}) at these coordinates.
351
352 Image processing operations like zooming, rotating or scaling can be implemented with texture mapping, by simply changing the vertices' positions or the textures coordinates at each vertex.
353
354 More often than not, the results of the linear interpolation are not integer, which means that the texture should be sampled between four adjacent pixels (figure~\ref{fig:bilinear}). In this case, for a better rendering, the four pixels should be read and their colors should be averaged (with different weights depending on the fractional parts). This process is called \textit{bilinear filtering} and is required to obtain a good rendering of MilkDrop presets (see figures \ref{fig:mdbilin} and \ref{fig:mdnearest}).
355
356 \begin{figure}
357 \centering
358 \includegraphics[height=30mm]{bilinear.eps}
359 \caption{Principle of bilinear texture filtering.}
360 \label{fig:bilinear}
361 \end{figure}
362
363 \begin{figure}
364 \centering
365 \includegraphics[height=70mm]{mdbilin.eps}
366 \caption{Rendering with bilinear filtering enabled.}
367 \label{fig:mdbilin}
368 \end{figure}
369
370 \begin{figure}
371 \centering
372 \includegraphics[height=70mm]{mdnearest.eps}
373 \caption{Rendering with bilinear filtering disabled (the nearest texel is used).}
374 \label{fig:mdnearest}
375 \end{figure}
376
377 In MilkDrop (and Milkymist), a special case of the texture mapping is used, as the only purpose is to distort a 2D image. The target surface is always a rectangle that covers the destination picture, on which the vertices are distributed evenly as a mesh which is always kept the same regardless of the applied distortion. The distortion is defined by altering the texture coordinates at each vertex.
378
379 Texture mapping, especially when bilinear filtering is desired, is a very compute intensive process, as explained in chapter \ref{ch:tmu}. A custom hardware accelerator has been developed, whose details are also covered in this chapter.
380
381 \section{Organization}
382 According to this background, we can derive the following project guidelines:
383
384 \begin{itemize}
385 \item develop a fast, resource-efficient and FPGA-optimized system-on-chip
386 \item develop an efficient memory subsystem
387 \item reuse a light-weight softcore CPU
388 \item partition carefully the tasks between hardware and software
389 \item develop custom hardware accelerators
390 \end{itemize}
391
392 The proposed solution is outlined in figure~\ref{fig:block}. Not all the blocks are ready at the time of this writing, nor all of them are within the scope of this Master's thesis, which focuses on computer architecture.
393
394 More specifically, the following components are not developed yet:
395 \begin{itemize}
396 \item microSD controller (the current prototype use a CF card through Xilinx SystemACE)
397 \item USB controller
398 \item Video input
399 \item IR receiver
400 \item MIDI controller
401 \item DMX512 controller
402 \end{itemize}
403
404 Hardware accelerators have been developed for the computation of vertices positions (PFPU) and for texture mapping (TMU), which have been found to be the most compute-intensive parts of the process. They are discussed in detail in chapters \ref{ch:pfpu} and \ref{ch:tmu}, respectively.
405
406 Graphics processing also requires a significant amount of memory bandwidth, which is discussed in chapter~\ref{ch:memory}.
407
408 Chapter~\ref{ch:intercon} describes the on-chip interconnect used to make the various blocks communicate with one another.
409
410 Finally, chapter~\ref{ch:sw} deals with the software execution environment and how the software is architected to obtain a good performances from the hardware.
411
412 \begin{figure}
413 \centering
414 \includegraphics[height=170mm]{soc_architecture.eps}
415 \caption{SoC block diagram.}
416 \label{fig:block}
417 \end{figure}
418
419
420 \chapter{Memory subsystem}
421 \label{ch:memory}
422 \section{Attacking the memory wall}
423 \label{sec:memorywall}
424 A recurrent point in many modern computer systems is the memory performance problem. The term \textit{memory wall} was coined~\cite{memorywall} to refer to the growing disparity of performance between logic such as CPUs and off-chip memories. While microprocessor performance has been improving at a rate of 60 percent per year, the access time to DRAM has been improving at less than 10 percent per year~\cite{memvscpu}.
425
426 Memory performance is measured with two metrics:
427 \begin{itemize}
428 \item \textit{bandwidth}, which is the amount of data that the memory system can transfer during a given period of time.
429 \item \textit{latency}, which is the amount of time that the memory system spends between the issue of a memory read or write request and its completion.
430 \end{itemize}
431
432 A memory system can have both high bandwidth and latency. If the logic making the memory accesses is able to issue requests in a pipelined fashion, sending a new request without waiting for the previous one to complete, high latency will not have an impact on bandwidth.
433
434 Latency and bandwidth are however linked in practice. Decreasing the latency also increases the bandwidth in many cases, because latency blocks sequential processes and prevents them from utilizing the full available bandwidth.
435
436 High-end processors for servers and workstations have a good ability to cope with relatively high memory latency, because techniques such as out-of-order execution and hardware multi-threading enable the processor to issue new instructions even though one is blocking on a memory access.
437
438 Thus, most of today's SDRAM controllers do a lot to optimize bandwidth but have little focus on latency. Bandwidth-optimizing techniques include:
439 \begin{itemize}
440 \item reordering memory transactions to maximize the page mode hit rate.
441 \item grouping reads and writes together to reduce write recovery times. Along with the above technique, this has a detrimental impact on latency because of the delays incurred by the additional logic in the address datapath.
442 \item running the system and the SDRAM in asynchronous clock domains in order to be able to run the SDRAM at its maximum allowable clock frequency. This requires the use of synchronizers or FIFOs, which have a high latency.
443 \item configuring the SDRAM at high CAS latencies in order to increase its maximum allowable clock frequency. This trend is best illustrated by the advent of DDR2 and DDR3 memories whose key innovation is to run their internal DRAM core at a submultiple of the I/O frequency with a wide data bus which is then serialized on the I/O pins. Since the internal DRAM core has a latency comparable to that of the earlier SDR and DDR technologies, the number of CAS latency cycles relative to the I/O clock is also multiplied.
444 \end{itemize}
445
446 An extreme example of these memory controller bandwidth optimizations is the MemMax\textregistered ~DRAM scheduler~\cite{memmax}. This unit sits on top of an already existing memory controller (which already has its own latency), adding seven stages of complex and high-latency pipelining that produces a good - but compute-intensive - DRAM schedule. The actual efficiency of this system has been questioned~\cite{dramqos} because of that significant increase in latency.
447
448 \section{Another approach}
449 The out-of-order execution and hardware multithreading processor optimizations discussed above that cope with high memory latency are complex and impractical in the context of small and cheap embedded systems, especially those targetted at FPGA implementations. For example, FPGA implementations of the OpenSPARC~\cite{opensparc} processor, which employs such optimizations, typically require an expensive high-end Xilinx XUPV5 board whose Virtex-5 FPGA alone costs roughly 13000 SEK.
450
451 Milkymist therefore uses simple in-order execution schemes in its CPU and in its accelerators, and strives to improve performance by focusing on reducing the memory latency.
452
453 The memory system features that improve latency (but also bandwidth) are discussed below.
454
455 \section{Memory system features}
456 \subsection{Single SDRAM and system clock domain}
457 The typical operating frequency of early SDR and DDR SDRAM (technologies that are prior to DDR2 and do not have a clock divider for the internal DRAM core) is close to the 100MHz frequency at which the FPGA is able to meet timing for the complete SoC. Thus, it was decided to run the DRAM and the system synchronously in order to remove the need for any clock domain transfer logic and reduce latency. The SDRAM I/O registers are clocked by the system clock, and timing of the SDRAM interface is met through the use of calibrated on-chip delay elements and delay-locked-loops (DLLs) to generate the off-chip SDRAM clock and the data strobes.
458
459 \subsection{Page mode control algorithm}
460 The Milkymist memory controller takes the so-called \textit{page mode gamble}: after an access, the DRAM row is left open in the hope that the next transaction to the memory bank will occur within the same row. If the memory controller is right, the read or write command can be immediately registered into the SDRAM, and only the CAS or write latency is incurred. If the memory controller is wrong, it must first precharge the DRAM bank and open the correct row, causing extra delays.
461
462 Thus, if the memory controller is often wrong, taking the page mode gamble will actually impact performance negatively. However, a study has shown~\cite{pagemode} that, with typical memory timings, the point at which the gamble pays off is for a page hit probability of 0.375 only, attainable with many practical memory access patterns.
463
464 Page hit probability is improved by the ability of the Milkymist memory controller to track open rows independently in each of the four memory banks that commercial SDRAM chips are equipped with.
465
466 This optimization positively affects both latency and bandwidth.
467
468 \subsection{Burst accesses}
469 \label{subsec:fmlburst}
470 All memory accesses are made using bursts, i.e. when an access for a word is made, the following words are also read or written. Burst mode is a feature of the SDRAM chips: only one read of write command is sent to them, and several words are transferred on subsequent clock cycles.
471
472 Using bursts frees the bus and DRAM control signals while other words are transferred, allowing the issue of new commands overlapping the data phase of the previous transaction.
473
474 Burst access is a form of prefetching that improves latency. It is only efficient when the prefetched data can be used by the requesting bus master. In the Milkymist system-on-chip, this is often the case:
475 \begin{itemize}
476 \item The CPU core has caches which access memory by complete cache lines. Thus, if the cache line length is a multiple of the burst length, the bursts can be easily fully memorized.
477 \item The video frame buffer repeatedly reads the same block of data in a sequential manner, and can easily make full use of the prefetched data assuming that is has sufficient on-chip buffer space.
478 \item The texture mapping unit also has a cache and a write buffer which work well with burst accesses. This is discussed in Chapter~\ref{ch:tmu}.
479 \end{itemize}
480
481 \subsection{Burst reordering}
482 \label{subsec:fmlborder}
483 This feature enables the use of the critical-word-first scheme in caches, reducing the overall memory latency.
484
485 When a request is issued at an address which is not a multiple of the burst length, the order of the words in the burst is changed so that the first word that comes out is the very word that is at the requested memory address. The prefetch address is then incremented and wraps to stay within the same burst.
486
487 For example, assuming a burst length of 4:
488 \begin{itemize}
489 \item a request at address 0 fetches words 0, 1, 2 and 3 (in this order)
490 \item a request at address 2 fetches words 2, 3, 0 and 1 (in this order)
491 \end{itemize}
492
493 \subsection{Pipelining}
494 \label{subsec:fmlpipe}
495 The memory bus of Milkymist~\cite{fml} is pipelined. During the transfer of the prefetched (burst) data, a new request can be issued. This is illustrated for a read request by the table below:
496
497 \begin{tabular}{|c|c|c|c|c|c|c|c|}
498 \hline
499 \textbf{Address} & A1 & A1 & A1 & A2 & A2 & A2 & A2 \\
500 \hline
501 \textbf{Data} & -- & -- & M(A1) & M(A1+1) & M(A1+2) & M(A1+3) & M(A2) \\
502 \hline
503 \end{tabular}\\
504
505 \begin{tabular}{|c|c|c|c|}
506 \hline
507 \textbf{Address (cont.)} & -- & -- & --\\
508 \hline
509 \textbf{Data (cont.)} & M(A2+1) & M(A2+2) & M(A2+3) \\
510 \hline
511 \end{tabular}
512
513 Together with burst access, this helps acheiving high performance: the memory controller can hide DRAM latencies and row switch delays by issuing the requests to the DRAM in advance, while the previous transaction is still transferring data.
514
515 \section{Practical implementation}
516 \label{sec:memimpl}
517 The Milkymist SoC uses 32-bit DDR SDRAM, configured to its maximum burst length of 8. Since the DDR SDRAM transfers two words per clock cycles (one on each edge), this is turned by the I/O registers into bursts of four 64-bit words synchronous to the system clock.
518
519 \begin{table}
520 \centering
521 \begin{tabularx}{13cm}{|X|l|}
522 \hline
523 \textbf{Task} & \textbf{Required bandwidth} \\
524 \hline
525 VGA frame buffer, 1024x768, 75Hz, 16bpp & 950Mbps \\
526 \hline
527 Distortion: texture mapping, 512x512 to 512x512, 30fps, 16bpp & 250Mbps \\
528 \hline
529 Live video: texture mapping, 720x576 to 512x512 with transparency, 30fps, 16bpp & 300Mbps \\
530 \hline
531 Scaling: texture mapping, 512x512 to 1024x768, 30fps, 16bpp & 500Mbps \\
532 \hline
533 Video echo: texture mapping, 512x512 to 1024x768 with transparency, 30fps, 16bpp & 900Mbps \\
534 \hline
535 NTSC input, 720x576, 30fps, 16bpp & 200Mbps \\
536 \hline
537 Software and misc. & 200Mbps \\
538 \hline
539 \textbf{Total} & \textbf{3.3Gbps} \\
540 \hline
541 \end{tabularx}
542 \caption{Estimate of the memory bandwidth consumption.}\label{tab:membw}
543 \end{table}
544
545 The memory is run at 100MHz, yielding a peak theoretical bandwidth of 6.4Gbps, which is more than enough for the intended video synthesis application (table~\ref{tab:membw}). This bandwidth is however never attained: events such as switching DRAM rows which takes significant time and, to a lesser extent, DRAM refreshes introduce dead times on the data bus. We will see in section~\ref{sec:memperf} that such an oversizing of the off-chip memory is needed if we want to keep the memory system simple.
546
547 \begin{figure}[H]
548 \centering
549 \includegraphics[height=85mm]{hpdmc_block.eps}
550 \caption{Block diagram of the HPDMC architecture.}\label{fig:hpdmc_block}
551 \end{figure}
552
553 The architecture of the memory controller, called HPDMC (for ``High Performance Dynamic Memory Controller''), is outlined in figure~\ref{fig:hpdmc_block}.
554
555 The control interface is used by the system to configure the controller, and also to issue the start-up sequence to the SDRAM. Indeed, SDRAM chips require a sophisticated sequence of commands upon power-up. In many memory controller designs, a hardware finite state machine is used to issue this command sequence. In order to save hardware resources, the system used  here leaves this task to the software, and, for this purpose, includes a ``bypass MUX'' that routes directly a configuration and status register of HPDMC to the SDRAM command and address pins. Once the SoC has run a software routine that sends the correct initialization sequence to the SDRAM, it switches permanently the bypass MUX to the ``SDRAM management unit'' and can use off-chip memory normally.
556
557 The SDRAM management unit is a finite state machine that translates the two high-level memory commands ``read burst at address'' and ``write burst at address'' into a series of lower-level commands understandable by the SDRAM chips (precharge bank, select row, read from row, etc.). The management unit is responsible for keeping track of the open rows, detecting page hits, switching rows, and issuing periodic DRAM refresh cycles.
558
559 The management unit is connected to the ``data path controller'', that follows the activities performed by the management unit in order to decide the direction of the bidirectional I/O pins (they should be set as outputs for writes and as input for reads). The data path controller is also responsible for sending signals to the management unit that indicate if it is safe to perform certain low-level operations. For example, the \verb!read_safe! signal goes low immediately after a read command is issued, because if another one were sent immediately after, the two resulting bursts would overlap in time and this could not work because there is only one set of data pins. Eventually, the data path controller takes into account the SDRAM write and read latencies to generate an acknowledgement signal when the data is actually there (or needs to be sent to the SDRAM) after a ``read row'' or ``write row'' command has been sent to the SDRAM.
560
561 Finally, the bus interface is a piece of glue logic that connects the SoC pipelined memory bus (FML) to the data path controller and the management unit.
562
563 HPDMC has been implemented in Verilog HDL, tested and debugged in RTL simulation using a DDR SDRAM Verilog model from Micron, integrated into the SoC, synthesized into FPGA technology, and eventually calibrated and tested by software routines running on the actual hardware.
564
565 This design of memory controller, specifically crafted for the Milkymist project and released under the GNU GPL license on the internet, has been picked up by the NASA for a software defined radio project and may be put up onboard the international space station in 2011. Gregory Taylor, Electronics Engineer at the NASA Jet Propulsion Laboratory, wrote:
566
567 \textit{While searching for a suitable SDRAM controller for the Jet Propulsion Laboratory's Software-Defined Radio onboard NASA's CoNNeCT experiment, I found S\'ebastien's HPDMC SDRAM controller on OpenCores.org. We needed a controller that was both high performance and well documented. Though the original HPDMC controller was designed for DDR SDRAM with a 32-bit bus, S\'ebastien clearly explained the modifications necessary to adapt the controller to our Single Data Rate, 40-bit wide SDRAM chip. I found the code to be well documented and easy to follow. The performance has met our requirements and the FPGA size requirement is small.}
568
569 \textit{The Communication Navigation and Networking Reconfigurable Testbed (CoNNeCT) experiment to be installed onboard the ISS is designed for the next generation of SDRs conforming to the Space Telecommunications Radio Systems (STRS) open architecture standard. The HPDMC controller will likely find its way into one or more loadable waveform payloads in the JPL SDR, and perhaps be used in other NASA projects as well. It may eventually find its way into deep space.}
570
571 \section{Performance measurement}
572 \label{sec:memperf}
573 \subsection{Introduction}
574 We wanted to validate and characterize the memory system performance (actual latency and bandwidth) and get an upper bound of of its ability to sustain loads, by extrapolating the maximum bandwidth one could get assuming the memory access time remains constant.
575
576 Since the memory performance depends on the particular access pattern that the system makes (because of the controller taking the page mode gamble, we wanted to take the measurements on the real system while it is rendering video effects in order to get an accurate result.
577
578 \subsection{Method}
579 A logic core has been added to the SoC that snoops on the memory bus activity in order to report the average latency and bandwidth.
580
581 That logic core exploits properties of the FastMemoryLink signaling in order to reduce its complexity to two counters that measure, for a given time period, the number of cycles during which the strobe and acknowledgement signals are active. Several parameters can then be computed:
582 \begin{itemize}
583 \item the \textbf{net bandwidth} carried by the link (based on the amount of data that the link has actually transferred)
584 \item the \textbf{average memory access time}, which is the time, in cycles, between the request being made to the memory controller and the first word of data being transferred.
585 \item the \textbf{bus occupancy} which is the percentage of time during which the link was busy and therefore unavailable for a new request.
586 \end{itemize}
587
588 Every FastMemoryLink transaction begins with the assertion of the strobe signal. Then, after one or more wait cycles, the memory controller asserts the acknowledgement signal together with the first word of data being transferred. The next cycle, the strobe signal is deasserted (unless a new transaction begins) while the next word in the burst is being transferred. A new transaction can start with the assertion of the strobe signal even if a burst is already going on (pipelining). See figure~\ref{fig:fmltransactions} for an example.
589
590 \begin{figure}
591 \centering
592 \includegraphics[height=40mm]{fmltransactions.eps}
593 \caption{FML transactions.} \label{fig:fmltransactions}
594 \end{figure}
595
596 In the equations that follow, these symbols are used:
597 \begin{itemize}
598 \item $f$ is the system clock frequency in Hz.
599 \item $T$ is the time during which the counters have been enabled.
600 \item $w$ is the width of a FML word in bits.
601 \item $n$ is the FML burst length.
602 \item $S$ is the number of cycles during which the strobe signal was active.
603 \item $A$ is the number of cycles during which the acknowledgement signal was active.
604 \end{itemize}
605
606 \paragraph{Net bandwidth.} By counting the number of cycles for which the acknowledgement signal was active, one gets the number of transactions. Since each transaction carries exactly a burst of data, which is $w \cdot n$ bits in size, the volume of data transferred is given by $w \cdot n \cdot A $. Thus, one can derive the net bandwidth as:
607 \begin{equation}
608 \beta = \frac{w \cdot n \cdot A}{T}
609 \end{equation}
610
611 \paragraph{Average memory access time.} On the bus, a master is waiting when the strobe signal is asserted but the acknowledgement signal is not. Therefore, the total number of wait cycles is given by $S-A$. The average memory access time can thus be computed as:
612 \begin{equation}
613 \Delta = \frac{S-A}{A}
614 \end{equation}
615
616 \begin{figure}
617 \centering
618 \includegraphics[height=45mm]{fmlmax.eps}
619 \caption{Maximum utilization of a FML bus.} \label{fig:fmlmax}
620 \end{figure}
621
622 The average memory access time can be used to derive an upper bound on the maximum bandwidth that the memory system can handle. Indeed, FML is a pipelined bus which supports only one outstanding (waiting) transaction, so the case that uses the most bandwidth for a given memory access time is when the strobe signal is always asserted (figure~\ref{fig:fmlmax}) so that a new transaction begins as soon as the first word of the previous trasaction is transferred.
623
624 Therefore, only a fraction $\alpha$ of the peak bandwidth $f \cdot w$ can be used at most, and we have:
625 \begin{equation}
626 \alpha = \textrm{max}(1, \frac{n}{\Delta+1})
627 \end{equation}
628
629 The maximum bandwidth is:
630 \begin{equation}
631 \beta_{max} = \alpha \cdot f \cdot w
632 \end{equation}
633
634 \paragraph{Bus occupancy.} The bus is busy when the strobe signal is asserted. The bus occupancy is therefore given by:
635 \begin{equation}
636 \epsilon = \frac{S}{T \cdot f}
637 \end{equation}
638
639 By using this method, a very simple piece of hardware added to the system can yield to the retrieval of interesting information about the performance of the memory system.
640
641 \subsection{Results}
642 Results are summarized in table~\ref{tab:memperformance}. The first line corresponds to a system running the demonstration firmware with the video output enabled at the standard VGA mode of 640x480 at 60Hz (therefore continuously scanning the screen with data from system memory), but not rendering a preset. The other lines represent the results while the demonstration firmware is rendering different MilkDrop presets, still at the same video resolution.
643
644 \begin{table}
645 \centering
646 \begin{tabular}{|l|l|l|l|l|l|}
647 \hline
648 \textbf{Patch} & $\beta$ & $\epsilon$ & $\Delta$ & $\alpha$ & $\beta_{max}$ \\
649 \hline
650 Idle & 292 & 7 \% & 5.51 & 61 \% & 3932 \\
651 \hline
652 Geiss - Bright Fiber Matrix 1 & 990 & 28 \% & 6.37 & 54 \% & 3474 \\
653 \hline
654 Geiss - Swirlie 3 & 1080 & 32 \% & 6.71 & 52 \% & 3320 \\
655 \hline
656 Geiss - Spacedust & 1021 & 29 \% & 6.47 & 54 \% & 3427 \\
657 \hline
658 Illusion \& Rovastar - Snowflake Delight & 1399 & 39 \% & 6.28 & 55 \% & 3516 \\
659 \hline
660 Rovastar \& Idiot24-7 - Balk Acid & 1427 & 41 \% & 6.38 & 54 \% & 3469 \\
661 \hline
662 \end{tabular}
663 \caption{Memory performance in different conditions (Milkymist 0.5.1). Bandwidths are in Mbps.}\label{tab:memperformance}
664 \end{table}
665
666 It is difficult to compare these results to those of other memory controllers as they are usually not published (or not measured at all).
667
668 However, two conclusions can be drawn:
669 \begin{itemize}
670 \item there are enough occupancy and bandwidth margins for the system to operate at higher resolutions and/or color depths than 640x480 and 16 bits per pixel. The 3.3 Gbps bandwidth requirement that was estimated in section~\ref{sec:memimpl} seems attainable, although challenging.
671 \item to go further, an ``out-of-order'' memory controller can be envisioned. Such a controller would have a split transaction bus (allowing a larger number of outstanding transactions, thus minimizing the impact that latency has on bandwidth) and would be able to reorder pending memory transactions to maximize the page hit rate.
672 \end{itemize}
673
674 \chapter{SoC interconnect}
675 \label{ch:intercon}
676 This chapter explains how the different interconnect busses work, what their features are, why they are there, and how they are communicate with each other.
677
678 The general SoC block diagram and its interconnect is outlined in figure~\ref{fig:block}.
679
680 \section{General SoC interconnect: the Wishbone bus}
681 Wishbone~\cite{wishbone} is a general purpose royalty-free SoC bus with open specifications, advocated by the maintainers of the OpenCores.org website.
682
683 Wishbone is a synchronous sequential bus with support for variable latency (wait states) through the use of an acknowledgement signal that marks the end of the transaction. Burst modes (automatic transfer of consecutive words) are supported and are configurable on a per-transaction basis (i.e. bursts of arbitrary lengths and single-word transactions can be freely mixed on the same bus). However, there is no pipelining.
684
685 Wishbone is used around the SoC's LatticeMico32 CPU core and for simple DMA masters which have modest requirements of bandwidth and of volume of transferred data. As explained in Section~\ref{sec:fmlbrg}, connecting DMA masters that transfer small amounts of data (which can fit in the L2 cache) to the same bus as the CPU simplifies dealing with cache coherency issues.
686
687 The data width used for the Wishbone bus is 32, yielding a peak bandwidth of 3.2Gbps when the system is running at 100MHz.
688
689 \section{Configuration and Status Registers: the CSR bus}
690 Milkymist uses memory-mapped I/O through configuration and status registers.
691
692 If these registers were directly accessed by the Wishbone CPU bus, two problems would arise:
693 \begin{itemize}
694 \item Connecting all peripherals on the same Wishbone bus involves large multiplexers and high fanout signals, posing routing and timing problems.
695 \item Wishbone requires the generation of an acknowledgement signal by each slave core. This signal is useful in many cases, as it supports peripherals with a variable latency. However, configuration and status register files are usually implemented with actual registers (flip flops) or SRAM, which can always be accessed in one clock cycle. Thus, there is no need for variable latency and the acknowledgement signal. Keeping this signal for the configuration and status registers wastes hardware resources and development time.
696 \end{itemize}
697
698 To alleviate these problems, the CSR bus has been developed~\cite{csr} and used in the system through a bus bridge.
699
700 The CSR bus is a simpler bus than Wishbone, where all transfers are done in one cycle. It has an interface similar to that of synchronous SRAM, consisting only of address, data in, data out and write enable pins and clocked by the system clock.
701
702 A bridge connects the CSR bus to the CPU Wishbone bus, to allow transparent memory-mapped access to the configuration and status registers by the software. This bridge includes registers for all the signals crossing the two busses, relaxing the timing constraints.
703
704 \section{High-throughput memory access bus: the FML bus}
705 FastMemoryLink (FML)~\cite{fml} was co-designed with HPDMC (the memory controller) as a on-chip bus tailored to access SDRAM memories at high speed while keeping the memory controller simple. Its key features are listed below.
706
707 \subsection{Variable latency}
708 SDRAM latency varies a lot depending on the state of the SDRAM at the time the request is issued on the bus. It depends on whether the SDRAM was in the middle of a refresh cycle, whether the bank needs to be precharged, and whether a new row needs to be activated. Therefore, FML provides support for a variable number of wait states, defined by the memory controller, through the use of an acknowledgement signal similar to that of Wishbone.
709
710 \subsection{Burst only}
711 SDRAM is best accessed in burst mode (see subsection~\ref{subsec:fmlburst}).
712
713 However, enabling or configuring burst mode is a relatively lengthy and complex operation, requiring a reload of the SDRAM mode register which takes several cycles. Furthermode, supporting multiple burst lengths makes the scheduling of the transfers more complex to avoid ``overlapping'' transfers that would create conflicts at the data pins.
714
715 Therefore, in order to greatly simplify the memory controller, all transfers on FML are made using a fixed and pre-defined burst length.
716
717 \subsection{Burst reordering}
718 This was discussed in subsection~\ref{subsec:fmlborder}.
719
720 \subsection{Pipelining}
721 The benefits of this feature have already been discussed in subsection~\ref{subsec:fmlpipe}.
722
723 Pipelined requests may come from the same core that issued the initial transfer, or from another core. The FML arbiter would then pipeline the request coming from the other core.
724
725 \subsection{Usage}
726 The data width used for the FML bus is 64, yielding a peak bandwidth of 6.4Gbps when the system is running at 100MHz. This is twice the peak bandwidth of the Wishbone bus. Furthermore, this bus provides a short path to the memory controller, reducing latency and therefore potentially further increasing effective bandwidth, as discussed in Section~\ref{sec:memorywall}.
727
728 Peripherals directly connected to FML are typically those which transfer large amounts of data (that would exceed the capacity of the L2 cache presented in section~\ref{sec:fmlbrg}) and which have high bandwidth requirements (and therefore can take advantage of the bandwidth and latency improvement compared to Wishbone).
729
730 In the Milkymist SoC, they are comprised of:
731 \begin{itemize}
732 \item the VGA output controller, which needs to continously scan a frame buffer up to several megabytes in size to generate the video signal.
733 \item the (planned) video input, which writes, every second, dozens of digitized video frames weighting hundreds of kilobytes each.
734 \item the texture mapping unit (chapter~\ref{ch:tmu}), which needs to deal with large textures at high speed.
735 \end{itemize}
736
737 \section{Bridging Wishbone to FML}
738 \label{sec:fmlbrg}
739 For Wishbone masters (like the CPU) to access SDRAM transparently, it is necessary to bridge the FML bus to the Wishbone bus.
740
741 FML is a burst-only bus with a fixed burst length, while with Wishbone, bursts are optional and configured on a per-transaction basis. To be efficient, the bridge must therefore be able to store data and slice it to meet the transfer size requirements of the Wishbone and FML transactions.
742
743 A traditional write-back cache with a line length equal to the FML burst length provides an elegant solution to this problem. This cache is referred to as the ``L2 cache'', because, from the CPU point of view, it provides a second level of cache relative to its integrated instruction and data caches.
744
745 \section{Cache coherency}
746 \label{sec:coherency}
747 \subsection{Coherency issues around the CPU (L1) cache}
748 The LatticeMico32 CPU (section~\ref{sec:mico32}) uses a write-through cache without hardware coherency. Thus, the following operations must be done by the software to ensure cache coherency:
749 \begin{itemize}
750 \item Before reading DMA data from a peripheral using shared memory, the L1 cache should be cleared as it may hold an outdated copy of the data.
751 \item When writing DMA data to a peripheral using shared memory on the Wishbone bus, no precaution should be taken. The CPU writes go directly to the bus, and end up in the L2 cache or the SDRAM where the peripheral will correctly retreive them.
752 \end{itemize}
753
754 It is noteworthy that the CSR address space is non-cacheable, therefore no cache-related precaution should be taken when reading or writing CSRs.
755
756 \subsection{Coherency issues around the Wishbone-FML (L2) cache}
757 The Wishbone-FML bridge provides very limited support for cache coherency. Cache coherency issues arise because of the masters directly connected to the FML bus:
758 \begin{itemize}
759 \item The CPU may read a cached copy of a data that has been modified by a FML master.
760 \item A FML master may read a value that has been modified by the CPU in the cache (dirty line) but not flushed to the SDRAM.
761 \item A FML master may update a value in SDRAM but not in the cache. The line may then go dirty, and, when flushed, will erase the value written by the FML master.
762 \end{itemize}
763
764 Because cache coherency is expensive to implement in hardware, the task of managing the coherency of caches has been moved almost entirely to the software. The bridge exposes an interface for the software to invalidate cache lines, flushing them to the SDRAM if they are dirty. On the software side, device drivers should use this interface appropriately when transferring data with hardware units that use shared memory.
765
766 The only form of hardware cache coherency the system has is related to the video frame buffer. The VGA signal generator is connected directly to the SDRAM bus, because the frame buffer is continuously scanned and is too large to fit entirely in the cache.
767
768 However, it is very common that software modifies only a few pixels on the screen. If there was no hardware cache coherency at all, it would be tricky to implement a software mechanism that flushes the bridge cache at appropriate times. A solution can be to flush the cache every time a pixel or a group of pixels are written (which can be extremely slow if only small regions of the screen are modified at a time). Another solution would be to periodically check if the frame buffer had been modified and flush the cache if it was.
769
770 Since those solutions are difficult to implement as they require a significant support from both the operating system and applications, it was chosen to make frame buffer read transactions by the VGA signal generator coherent with respect to the bridge cache. Every time the VGA signal generator fetches a burst of pixels, it first searches the bridge cache. If the data is in the cache, it is used. If not, the VGA signal generator fetches it from SDRAM (but does not replace any cache line).
771
772 This also makes it easier to write Milkymist frame buffer drivers within the frameworks of common operating systems, such as Linux (figure~\ref{fig:linux}).
773
774 \chapter{Texture mapping unit}
775 \label{ch:tmu}
776 High performance texture mapping was perhaps the most challenging and interesting part of the SoC design project. This chapter begins with the design of an efficient algorithm and continues with the hardware implementation of it, and in particular how it was pipelined and how its memory references are handled.
777
778 \section{Algorithm}
779 \subsection{Two-dimensional interpolation}
780 As underlined in section~\ref{sec:tm}, we need to interpolate linearly on a 2D polygon the X and Y texture coordinates according to known values on the vertices of the polygon.
781
782 Traditional GPUs use the triangle as the primitive polygon, because it allows them to draw any other polygon by splitting it into a series of triangles. We do not need such flexibility. For rendering MilkDrop presets, the surface to be drawn is always a mesh of rectangles whose edges are parallel to the borders of the screen (traditional GPUs draw the surface using a triangle decomposition similar to the one shown in figure~\ref{fig:tridec}). We can therefore choose, as the primitive polygon, the rectangle with edges parallel to the borders of the screen, which is much simpler to draw than arbitrary triangles.
783
784 \begin{figure}[htp]
785 \centering
786 \includegraphics[height=50mm]{tridec.eps}
787 \caption{Typical decomposition into triangular primitives of the MilkDrop rendering surface.}
788 \label{fig:tridec}
789 \end{figure}
790
791 We then split the 2D interpolation problem into 1D interpolation problems as follows:
792 \begin{itemize}
793 \item The X and Y texture coordinates are interpolated independently.
794 \item First, each coordinate is interpolated on the vertical edges of the rectangles (vertical interpolation) for each integer value of the ordinate.
795 \item For each integer value of the ordinate, the results from the vertical interpolation are interpolated again for each integer value of the abscissa (horizontal interpolation). This scans all the pixels within the rectangle.
796 \end{itemize}
797 The process is illustrated in figure~\ref{fig:rectinter}.
798
799 One could obtain the same result by starting with an horizontal interpolation followed by several vertical interpolations. However, when using a linear scan frame buffer (as Milkymist does), doing it in the proposed way yields output pixels whose memory addresses are consecutive in most cases (except when going to the next ordinate), which works well with the bursty nature of SDRAM accesses (subsection~\ref{subsec:fmlburst}) and the traditional organization of a cache.
800
801 \begin{figure}[htp]
802 \centering
803 \includegraphics[height=70mm]{rectinter.eps}
804 \caption{2D linear interpolation on a rectangle.}
805 \label{fig:rectinter}
806 \end{figure}
807
808 \subsection{One-dimensional interpolation}
809 The problem now boils down to performing one-dimensional linear interpolations. Given two points $A(x_{0}, y_{0})$ and $B(x_{1}, y_{1})$ with integer coordinates, we need to compute the ordinate $y$ of $M(x, y) \in (AB)$ for all the integer values of $x$ between $x_{0}$ and $x_{1}$. For now, we are not interested in bilinear filtering, so what we actually want is the best integer approximation $[y]$ of $y$ so that the texture is sampled to the nearest pixel.
810
811 In figure~\ref{fig:interalgo} we propose a fast and integer-only\footnote{And thus more suited to a resource-constrained hardware implementation.} algorithm, which was inspired by Bresenham's line drawing algorithm~\cite{bresenham}. Without loss of generality, we suppose that $x_{0} \leq x_{1}$ (the points can be reordered if this was not the case). We also suppose that $y_{0} \leq y_{1}$ (it is easy to modify the algorithm to handle the $y_{0} > y_{1}$ case as well\footnote{See the Verilog implementation in Milkymist (cores/tmu2/rtl/tmu2\_geninterp18.v).}).
812
813 \begin{figure}
814 \centering
815 \begin{boxedminipage}{13cm}
816 \begin{math}
817 Dy \leftarrow y_{1} - y_{0} \\
818 Dx \leftarrow x_{1} - x_{0} \\
819 Q \leftarrow Dy / Dx \footnote{/ is the integer division operator} \\
820 R \leftarrow Dy \% Dx \footnote{\% is the integer modulo operator}  \\
821 x \leftarrow x_{0} \\
822 \hspace{0cm} [y] \leftarrow y_{0} \\ % WA: latex doesn't like lines starting with [
823 e \leftarrow 0 \\
824 \textrm{result(x)} \leftarrow [y] \\
825 \textrm{\textbf{while}~} x < x_{1} \\
826 \textrm{~~~~~} x \leftarrow x + 1 \\
827 \textrm{~~~~~} [y] \leftarrow [y] + Q \\
828 \textrm{~~~~~} e \leftarrow e + R \\
829 \textrm{~~~~~\textbf{if}~} 2\cdot e > Dx \\
830 \textrm{~~~~~~~~~~} [y] \leftarrow [y] + 1 \\
831 \textrm{~~~~~~~~~~} e \leftarrow e - Dx \\
832 \textrm{~~~~~\textbf{end}} \\
833 \textrm{~~~~~result(x)} \leftarrow [y] \\
834 \textrm{\textbf{end}}
835 \end{math}
836 \end{boxedminipage}
837 \caption{One-dimensional linear interpolation algorithm.}
838 \label{fig:interalgo}
839 \end{figure}
840
841 The correctness of the algorithm lies in the fact that every time the result is being written, those conditions are verified (from which it can be derived that $[y]$ is the best integer approximation of $y$):
842 \begin{enumerate}
843 \item $|e| \leq \frac{Dx}{2}$ (which implies $|\frac{e}{Dx}| \leq \frac{1}{2}$)
844 \item The perfect (rational) interpolated value $y$ is equal to $y = [y] + \frac{e}{Dx}$.
845 \end{enumerate}
846
847 These conditions can be proven true by recursion:
848 \begin{enumerate}
849 \item For $x = x_{0}$, $e = 0$ therefore $|e| \leq \frac{Dx}{2}$. Let us now suppose that the hypothesis is true for a certain value of $x \geq x_{0}$, and prove that it is true for $x+1$.
850
851 The instructions that affect $e$ between two consecutive values of $x$ are $e \leftarrow e + R$ and, if $2\cdot e > Dx$, $e \leftarrow e - Dx$.
852
853 After the first instruction:
854 \begin{itemize}
855 \item if $e$ was negative or zero, we have $-\frac{Dx}{2} \leq e < Dx < \frac{3 \cdot Dx}{2} $ (because $0 \leq R < Dx$ and the recursion hypothese).
856 \item if $e$ was positive, it was inferior or equal to $\frac{Dx}{2}$ (because of the recursion hypothese), therefore we have $0 < e < \frac{3 \cdot Dx}{2} $.
857 \end{itemize}
858 After the second instruction, if we had $e > \frac{Dx}{2}$, we'll have $e < \frac{3 \cdot Dx}{2} - Dx$. Therefore, $e \leq \frac{Dx}{2}$. $\Box$
859
860 \item We need to prove that every time the result is being written, the following equation is verified:
861 \begin{equation}
862 \hspace{0cm} [y] + \frac{e}{Dx} = y_{0} + \frac{y_{1}-y_{0}}{x_{1}-x_{0}} \cdot (x - x_{0})
863 \end{equation}
864 For $x = x_{0}$, $[y] + \frac{e}{Dx} = y_{0}$, so the equation is verified. Let us now suppose that it is verified for a certain value of $x \geq x_{0}$, and prove that it is true for $x+1$.
865
866 It can be noted that the instructions within the ``if'' do not change the value of $[y] + \frac{e}{Dx}$. The only instructions that change the result between two consecutive values of $x$ are $[y] \leftarrow [y] + Q$ and $e \leftarrow e + R$. Therefore, after the loop iteration, we have:
867 \begin{equation}
868 \hspace{0cm} [y] + \frac{e}{Dx} = y_{0} + \frac{y_{1}-y_{0}}{x_{1}-x_{0}} \cdot (x - x_{0}) + Q + \frac{R}{Dx}
869 \end{equation}
870 \begin{equation}
871 \hspace{0cm} [y] + \frac{e}{Dx} = y_{0} + \frac{y_{1}-y_{0}}{x_{1}-x_{0}} \cdot (x - x_{0}) + \frac{y_{1}-y_{0}}{x_{1}-x_{0}} \\
872 \end{equation}
873 \begin{equation}
874 \hspace{0cm} [y] + \frac{e}{Dx} = y_{0} + \frac{y_{1}-y_{0}}{x_{1}-x_{0}} \cdot ((x + 1) - x_{0})
875 \end{equation}
876 $\Box$
877 \end{enumerate}
878
879 \subsection{Bilinear filtering}
880 \label{subsec:bilfpformat}
881 As outlined in section~\ref{sec:tm}, bilinear filtering is needed to obtain good rendering results.
882
883 We will therefore try to improve the previous algorithm so that we get a more precise, non-integer interpolation result. Preferably, the result should be in fixed point format so that it can be easily handled for the actual filtering stage (weighted average of adjacent pixels colors).
884
885 The first thing that comes to mind is to try to use the error value $\frac{e}{Dx}$. However, this would require an integer to fixed point division to be performed at each interpolated result (the horizontal interpolation alone would require two such operations per pixel), which is expensive.
886
887 A more elegant solution consists in multiplying all the texture coordinates by a power of 2, noted S (this is an inexpensive operation, as it can be implemented with a bit shift). Since the interpolation process is linear, the outputs are also multiplied by S --- but the precision is increased. In other words, the output of the interpolation stages comes directly in fixed point format, with $log_{2}(S)$ digits after the radix point.
888
889 Figure~\ref{fig:filtfromfp} illustrates how the bilinear filtering is done using the fixed point texture coordinates. The texture coordinates are noted X.i, X.f, Y.i and Y.f, with ``i'' denoting the integer part of the fixed point number (bits before the radix point) and ``f'' denoting the fractional part (bits after the radix point).
890
891 \begin{figure}[htp]
892 \centering
893 \includegraphics[height=85mm]{filtfromfp.eps}
894 \caption{Bilinear filtering using the fixed point texture coordinates.}
895 \label{fig:filtfromfp}
896 \end{figure}
897
898 The weights in the average should be proportional to the surface that the texel to be sampled with non-integer coordinates (the grey box on the figure) covers in each of the real texture pixels (numbered 1 to 4 on the figure). Thus, if $c_{1}$, $c_{2}$, $c_{3}$ and $c_{4}$ are respectively the color vectors of the texture pixels 1 to 4 and $c$ is the color vector of the result, we have:
899 \begin{equation}\label{eq:bfilter}
900 c = \frac{(S-X.f)(S-Y.f) \cdot c_{1} + X.f(S-Y.f) \cdot c_{2} + (S-X.f)Y.f \cdot c_{3} + X.fY.f \cdot c_{4}}{S^{2}}
901 \end{equation}
902
903 Since we are working with the RGB565 color format, having more than 6 extra bits of precision would not make a difference for the filtering. Therefore, we choose $S = 2^{6} = 64$.
904
905 \section{Performance considerations}
906 \subsection{Context}
907 \label{subsec:perfcontext}
908 To motivate the implementation choice of the texture mapping, we will study its execution time in the following  situation:
909 \begin{itemize}
910 \item The size of the source (texture) and destination pictures is 512x512.
911 \item The size of the primitive rectangles is 16x16.
912 \item We need at least 120 runs per second. Indeed, the renderer needs to distort the image, include live video, scale it, and apply the video echo effect 30 times per second (subsection~\ref{subsec:mdprinciple}). We therefore have approximately 8 ms of processing time at most (which corresponds to 31 megapixels per second). This is a very optimistic estimate: since scaling, inclusion of live video and the video echo effect work with resolutions greater than 512x512, these processes are expected to take more time than the 512x512 $\rightarrow$ 512x512 distortion.
913 \item The system clock is 100MHz.
914 \item The $2\cdot e > Dx$ test is always false (which is optimistic).
915 \item We optimistically do not take into account the extra instructions needed to handle interpolations with a negative slope ($y_{0} > y_{1}$).
916 \end{itemize}
917
918 For a software implementation, we use the cost estimates of table~\ref{tab:swcost}.
919
920 \begin{table}
921 \centering
922 \begin{tabular}{|l|l|}
923 \hline
924 \textbf{Operation} & \textbf{Cost} \\
925 \hline
926 Addition or subtraction & 1 cycle \\
927 \hline
928 Multiplication & 2 cycles \\
929 \hline
930 Division or modulo & 32 cycles \\
931 \hline
932 Bit shift & 1 cycle \\
933 \hline
934 Test (<, >, =, etc.) & 1 cycle \\
935 \hline
936 Conditional jump & 3 cycles \\
937 \hline
938 Assignment & free (which is optimistic) \\
939 \hline
940 Reading or writing to the frame buffer & 2 cycles \\
941 \hline
942 \end{tabular}
943 \caption{Estimates of the cost of common software operations.}\label{tab:swcost}
944 \end{table}
945
946 \subsection{Execution time of the interpolation algorithm}
947 For each 1D interpolation with n steps, we need the amount of time detailed in table~\ref{tab:intertime}. The steps are in the same order as in figure~\ref{fig:interalgo}.
948
949 \begin{table}
950 \centering
951 \begin{tabular}{|l|l|}
952 \hline
953 \textbf{Operation} & \textbf{Cycles} \\
954 \hline
955 2 subtractions & $2$ \\
956 \hline
957 Division & $32$ \\
958 \hline
959 Modulo & $32$ \\
960 \hline
961 Test & $n$ \\
962 \hline
963 Conditional jump & $3 \cdot n$ \\
964 \hline
965 3 additions & $3 \cdot n$ \\
966 \hline
967 Bit shift (multiply by 2) & $n$ \\
968 \hline
969 Test & $n$ \\
970 \hline
971 Conditional jump & $3 \cdot n$ \\
972 \hline
973 \textbf{Total} & $66 + 12 \cdot n$ \\
974 \hline
975 \end{tabular}
976 \caption{Detailed estimate of the execution time of the interpolation algorithm.}\label{tab:intertime}
977 \end{table}
978
979 \subsection{Total execution time}
980 Using the above formula with $n=15$, we can compute an estimate of the execution time of a software implementation (table~\ref{tab:swtmutime}).
981
982 1D interpolations need to be done twice, once for each texture coordinate.
983
984 The number of frame buffer reads is computed by considering that for each pixel written to the 512x512 destination picture, 4 pixels must be read from the source picture.
985
986 The cost of bilinear filtering is computed, for each destination pixel, with 4 subtractions, 8 multiplications, 4 additions and 1 bit shift times 3 color channels, which yields 75 cycles. This is optimistic as it does not take into account the time needed to decode the fixed point format.
987
988 \begin{table}
989 \centering
990 \begin{tabular}{|l|l|l|}
991 \hline
992 \textbf{Operation} & \textbf{Cycles} & \textbf{Time} \\
993 \hline
994 Vertical interpolation & 503808 & 5 ms \\
995 \hline
996 Horizontal interpolation & 8060928 & 81 ms \\
997 \hline
998 Framebuffer reads & 2097152 & 21 ms \\
999 \hline
1000 Bilinear filtering & 19660800 & 197 ms \\
1001 \hline
1002 Framebuffer writes & 524288 & 5 ms \\
1003 \hline
1004 \textbf{Total} & 30846976 & 308 ms \\
1005 \hline
1006 \end{tabular}
1007 \caption{Optimistic estimate of the execution time of software texture mapping.}\label{tab:swtmutime}
1008 \end{table}
1009
1010 According to this (yet optimistic) estimate, it becomes clear that a software implementation could not suffice, as the required performance is 8 ms. Even the vertical interpolation can hardly be implemented in software, as it would use alone more than 60\% of the CPU power (which is needed for other tasks). We need an overall speedup by a factor of more than 40, using hardware acceleration.
1011
1012 \section{Pipelined hardware implementation}
1013 \subsection{Strategy}
1014 \label{subsec:tmustrategy}
1015 Given the performance constraints and the slowness of software implementations, we decided to implement the complete texture mapping process in hardware.
1016
1017 It is expected that the memory latency for reading the frame buffer would be a performance-limiting factor. Instead of trying to alleviate its effects by using complex and potentially resource-intensive techniques such as advanced prefetching or non-blocking caches, we simply use a direct-mapped blocking texel cache providing simplicity and fast hit times, and design the rest of the texture mapping unit so that the memory read latency becomes the \textit{only} limiting factor.
1018
1019 With a direct-mapped texel cache having a hit rate of 90\%, a hit time of 1 cycle and a miss penalty of 9 cycles, the average memory access times is 1.8 cycles. With a 100MHz system clock, such a cache has a throughput of 55 megapixels per second, well above the optimistic estimate made in subsection~\ref{subsec:perfcontext}.\footnote{This is a quick estimate assuming a normal cache that does not support bilinear filtering. To implement bilinear filtering, the situation is more complex as the cache needs to look up 4 pixels at once. This is discussed in subsection~\ref{subsec:texelcache}.}
1020
1021 To make sure that the memory access time is the only limiting factor, it was chosen that the rest of the system should be designed to support a throughput of approximately one output pixel per clock cycle. This heuristic was influenced by the fact that it corresponds to a spatial implementation of the algorithm (i.e. with little or no time-based resource sharing of the hardware components) but does not require resource-intensive duplication of large hardware units either. A spatial implementation requires more area than a time-shared one, but it is simpler to understand, and needs fewer multiplexers and is less prone to routing congestions, making it easier to achieve timing closure in FPGAs.
1022
1023 A deeply pipelined implementation of the texture mapping algorithm was thus chosen, whose block diagram is depicted in figure~\ref{fig:tmublock}. Many of the stages have internal pipeline sub-stages, and they are detailed below.
1024
1025 \begin{figure}[htp]
1026 \centering
1027 \includegraphics[height=165mm]{tmublock.eps}
1028 \caption{Block diagram of the texture mapping unit architecture.}
1029 \label{fig:tmublock}
1030 \end{figure}
1031
1032 \subsection{Vertex fetch engine}
1033 There is not much to say about this stage, which is a straightforward finite state machine-based Wishbone bus master that fetches the texture coordinates of each vertex from the system memory, and sends them down the pipeline to the vertical interpolator.
1034
1035 The vertex fetch engine is connected to the lower-bandwidth Wishbone bus because this saves resources compared to FML (which has a wider datapath) and makes it easier to handle cache coherency issues (section~\ref{sec:coherency}).
1036
1037 \subsection{Interpolators}
1038 The horizontal and vertical interpolators are both implemented in the same way. They are vector interpolators, which contain two scalar interpolators (figure~\ref{fig:vectinter}, one for each texture coordinate). Each scalar interpolator contains additional internal pipeline sub-stages, as described in figure~\ref{fig:pipeinter}.
1039
1040 The vertical interpolator contains two vector interpolators, one for each vertical edge of the rectangle.
1041
1042 \begin{figure}[htp]
1043 \centering
1044 \includegraphics[height=70mm]{vectinter.eps}
1045 \caption{Vector interpolator.}
1046 \label{fig:vectinter}
1047 \end{figure}
1048
1049 \begin{figure}[htp]
1050 \centering
1051 \includegraphics[height=85mm]{pipeinter.eps}
1052 \caption{Pipelined scalar interpolator.}
1053 \label{fig:pipeinter}
1054 \end{figure}
1055
1056 \subsubsection{Stages of the scalar interpolator}
1057 \paragraph{Stage A: Dx and Dy computation.} This stage computes the two differences $y_{1} - y_{0}$ and $x_{1} - x_{0}$. It is based on simple registered arithemetic combinatorial functions, which compute the two differences in one clock cycle.
1058
1059 \paragraph{Stage B: Q and R computation.} The next operation is to perform the Euclidian division of Dy by Dx. The hardware does so by using the restoring division method~\cite{restdiv}, which takes as many cycles as there are quotient digits (our implementation has 18).
1060
1061 In order to keep the resource usage low, the divider is not pipelined. After operands are sent to it, it stalls transmissions from the upstream stage for several cycles until the division is complete.
1062
1063 \paragraph{Stage C: Interpolation loop.}
1064 Finally, the core of the algorithm (the ``while'' loop from figure~\ref{fig:interalgo}) is implemented in the last stage. This unit receives the Q and R values from the dividers, as well as the start $y_{0}$ value and the range $x_{0}$ to $x_{1}$ (which are forwarded through the previous stages). It then sends the series of interpolated values $[y]$ for $x_{0} \leq x < x_{1}$.
1065
1066 The throughput of the stage is one interpolation point per clock cycle. While the interpolation is taking place, transmission of new parameters from the upstream stage is stalled. This justifies the choice of a slow but low-area restoring divider in stage B: with a typical rectangle size of 16, the processing times of the interpolation loop and of the divider are roughly the same, making the pipeline balanced.
1067
1068 \subsection{Clamping/wrapping}
1069 This unit processes interpolated texture points whose coordinates are beyond the boundaries of the texture (i.e. they are negative or exceed the texture's horizontal or vertical resolution).
1070
1071 There are two, selectable, ways of dealing with them:
1072 \begin{itemize}
1073 \item \textit{clamping}, which consists in replacing an out-of-range coordinate with 0 (if it was negative) or with the horizontal or vertical resolution of the texture minus one (if it was too large).
1074 \item \textit{wrapping}, which repeats the texture and consists in computing the positive modulo of each coordinate with respect to the horizontal or vertical texture resolution. In order to avoid using an expensive fast divider, only textures whose sizes are a power of 2 are supported for wrapping. This enables the replacement of the divider with a bitwise AND operation, which is way less expensive. The problem of negative texture coordinates is solved by simply masking out the sign bit, which yields the correct result as the coordinates are represented in two's complement format.
1075 \end{itemize}
1076
1077 This stage is implemented by simple arithmetic combinatorial functions, which are registered and pipelined on two sub-stages to meet timing requirements.
1078
1079 \subsection{Address generator}
1080 The address generator is a simple arithmetic circuit that turns the floating point texture coordinates into the four memory addresses of the pixels they cover, and the destination coordinate into the corresponding memory address in the destination frame buffer. It is pipelined on three sub-stages to meet timing goals.
1081
1082 The formula used to convert a coordinate $(x,y)$ into a pixel address $A$ within a 16bpp frame buffer starting at $A_{base}$ and with an horizontal resolution $H$ is the following:
1083 \begin{equation}\label{eq:fbadr}
1084 A = A_{base} + (H \cdot y + x) \cdot 2
1085 \end{equation}
1086
1087 \subsection{Texel cache}
1088 \label{subsec:texelcache}
1089 \subsubsection{Presentation}
1090 Once the addresses of the four texture pixels have been computed, the next step is to retrieve data from the memory. This should be done fast: to meet the performance goal of 31 megapixels per second at the output of the texture mapping unit, the texel cache must be able to fetch at least 124 megapixels per second. This is, on average, at least 1.24 pixel per clock cycle with a 100MHz system clock.
1091
1092 In consistence with the heuristic made at subsection~\ref{subsec:tmustrategy} that consists in designing the system for a performance of one output pixel per clock cycle in the absence of memory read delays, the texel cache should be able to service the four request ports (called \textit{channels}) in one clock cycle if all the channels hit the cache.
1093
1094 Channel are numbered as follows (see figure~\ref{fig:bilinear}):
1095 \begin{itemize}
1096 \item Channel 1 fetches the \textit{base} pixel, that is to say, the pixel at the coordinates obtained by flooring the non-integer texture coordinates. It is always active.
1097 \item Channel 2 fetches the pixel at the right of the base pixel. It is active when the X texture coordinate has a non-zero fractional part.
1098 \item Channel 3 fetches the pixel at the bottom of the base pixel. It is active when the Y texture coordinate has a non-zero fractional part.
1099 \item Channel 4 fetches the pixel at the bottom-right of the base pixel. It is active when both the X and Y texture coordinate have a non-zero fractional part.
1100 \end{itemize}
1101
1102 \subsubsection{Separate vs. shared caches}
1103 The obvious solution seems have one separate cache per channel. However, this solution is not optimal in terms of speed and memory efficiency. For example, let us take the case when the texture mapping consists in zooming the texture by a factor of 2 (the texture coordinates at each vertex are the vertex coordinates divided by 2). Assuming an empty cache at the beginning, the sequence of events is as follows:
1104 \begin{enumerate}
1105 \item The interpolated fixed-point texture coordinates are (0, 0). Channel 1 misses its cache for a fetch of the pixel at (0, 0). Since the coordinates are integer, channels 2, 3 and 4 are idle and do not need to fetch data.
1106 \item The texture coordinates become (0.5, 0). Channel 1 hits its cache for the pixel at (0, 0). However, channel 2 misses its cache for the pixel at (1, 0) and a new memory request needs to be performed, even though the pixel at (1, 0) is in the cache of channel 1 (it was part of the burst that fetched the (0, 0) pixel). Channels 3 and 4 are idle, since the Y coordinate is integer.
1107 \end{enumerate}
1108 The problem repeats every time the X texture coordinate crosses a memory burst boundary, and is also present in the Y direction with channels 3 and 4. In total, the texel cache uses \textit{four times} as much memory bandwidth as it would use if it were able to share data between the channels' respective caches.\footnote{Assuming at least two complete horizontal lines of pixels from a primitive rectangle fit in the cache, which is generally the case.} Zooming (locally or globally) is a very common operation, so the issue needs to be addressed.
1109
1110 A more efficient solution, which has been retained, consists therefore in having a single multi-ported data store.
1111
1112 \subsubsection{Implementation}
1113 Our implementation is based on the traditional direct-mapped cache, but using quad-port SRAM for the data and tag stores. Quad-port SRAM can be mapped to FPGA technologies at a moderate cost by using two primitive dual-port SRAMs in which the data is replicated. During normal operation (hits), each port serves one channel, and, when refilling the cache on a miss, reading is disabled and two of the ports (one per primitive dual-port SRAM) are used to feed the data into the RAMs.
1114
1115 A simplified block diagram of the texel cache is given in figure~\ref{fig:tcarch}. This block diagram does not include all of the logic needed to handle pipeline stalls and lacks the ``valid'' bits of the tags.
1116
1117 \begin{figure}[htp]
1118 \centering
1119 \includegraphics[height=100mm]{tcarch.eps}
1120 \caption{Architecture of the four-channel texel cache.}
1121 \label{fig:tcarch}
1122 \end{figure}
1123
1124 At each clock cycle, the texel cache processes, in a pipelined manner,\footnote{The SRAMs are registered, in order to improve timing and to map to the block RAMs of common modern FPGAs which always contain an internal register.} four memory addresses from each channel if they hit the caches. The ``hit'' signal is kept high and the pipeline is always running.
1125
1126 In case of a miss, the ``hit'' signal goes low (stalling the pipeline), and the priority encoder and the multiplexer (MUX) select one of the missed addresses (there can be one or many). The FastMemoryLink master issues a memory transaction to retrieve the data from the system memory, replaces the contents of the cache line and rewrites the tag. The address now becomes a cache hit. If no other address misses the cache, the texel cache has successfully handled the 4-channel transaction and the ``hit'' signal goes high again to proceed to the next. Otherwise, the process repeats until all addresses hit the cache. Our design does not take advantage of the pipelining feature of the FastMemoryLink bus and issues requests sequentially.
1127
1128 \subsubsection{Inter-channel cache conflicts}
1129 An \textit{inter-channel cache conflict} (ICCC) occurs when two or more channels request different addresses that have different tags but map to the same cache line.
1130
1131 This condition is not desirable. With our implementation, the texel cache would go into an infinite loop fetching data from the memory in an attempt to make all channels hit the cache --- which it can never achieve --- until it is manually reset.\footnote{As a safety measure, it is therefore recommended that software drivers for the texture mapping unit check for the possibility of ICCC conditions before running the TMU and report an error if an ICCC is possible.}
1132
1133 This choice has been made for two reasons: first, adding hardware to deal with ICCCs would yield poor performance anyway as some memory bursts would be there only for retrieving one pixel and solving the conflict,\footnote{This is true only if we keep a direct-mapped cache. With a multiple-way set-associative cache and a smart replacement policy that allocates one specific way to each conflicting channel when an ICCC occurs, the hardware can both deal with ICCCs and yield high performance. However, it is more complex and expensive. Furthermore, when keeping a direct-mapped cache, it makes sense to add hardware that would deal with infrequent cases of ICCCs such as those arising when wrapping at texture boundaries.} second, ICCCs are easy to avoid for our purposes, and we will see how.
1134
1135 For simplicity, we use the pixel (2 bytes) as unit. In the equations that follow:
1136 \begin{itemize}
1137 \item $H$ is the horizontal texture resolution in pixels.
1138 \item $V$ is the vertical texture resolution in pixels.
1139 \item $N_{l}$ is the number of pixels a cache line can hold. It is equal to the line size in bytes divided by 2.
1140 \item $N_{c}$ is the total number of pixels the texel cache can hold. It is equal to the cache size in bytes (not counting the tag memory) divided by 2.
1141 \end{itemize}
1142
1143 \paragraph{Characterization of cache conflicts.} A pixel at address $a_{p}$ (measured in pixels, i.e. 2-byte words) is mapped to the cache line indexed by:
1144 \begin{equation}
1145 l_{p} = \left\lfloor \frac{a_{p}}{N_{l}} \right\rfloor \pmod{\frac{N_{c}}{N_{l}}}
1146 \end{equation}
1147 Thus, two pixels at addresses $a_{1}$ and $a_{2}$ conflict in the cache if and only if:
1148 \begin{equation}\label{eq:cacheconflict}
1149 \begin{cases}
1150 |a_{1}-a_{2}| \geq N_{l} \\
1151 \left\lfloor \frac{a_{1}}{N_{l}} \right\rfloor \equiv \left\lfloor \frac{a_{2}}{N_{l}} \right\rfloor \pmod{\frac{N_{c}}{N_{l}}}
1152 \end{cases}
1153 \end{equation}
1154
1155 Texture clamping only causes one or more channel addresses to be equal, and therefore does not introduce additional cases of ICCCs. However, texture wrapping does introduce new dispositions of the channels within the texture, and new ICCC conditions.
1156
1157 \paragraph{Conflicts between channels 1 and 2 (or 3 and 4).}
1158 \begin{figure}[htp]
1159 \centering
1160 \includegraphics[height=55mm]{chdisp_common.eps}
1161 \caption{Disposition of the channels within the texture, general case.}\label{fig:chdispcommon}
1162 \end{figure}
1163 \begin{figure}[htp]
1164 \centering
1165 \includegraphics[height=55mm]{chdisp_vwrap.eps}
1166 \caption{Disposition of the channels within the texture, vertical wrapping.}\label{fig:chdispvwrap}
1167 \end{figure}
1168 The addresses $a_{A}$ and $a_{B}$ of these two channels can be separated by either:
1169 \begin{itemize}
1170 \item 1 pixel in the most common case (sampling in the middle of the texture, see figure~\ref{fig:chdispcommon}). This cannot cause inter-channel cache conflicts.
1171 \item $H-1$ pixels if texture wrapping is enabled and the texture is sampled at one of its vertical edges (figure~\ref{fig:chdispvwrap}). In this case, the condition $|a_{A}-a_{B}| \geq N_{l}$ is often verified (except for small textures where $H-1 < N_{l}$). To make sure that there will be no ICCC, we must thus make sure that the following condition is also verified:
1172 \begin{equation}\label{eq:noconflictwrap1}
1173 \left\lfloor \frac{a_{A}}{N_{l}} \right\rfloor \not \equiv \left\lfloor \frac{a_{A}+H-1}{N_{l}} \right\rfloor \pmod{\frac{N_{c}}{N_{l}}}
1174 \end{equation}
1175
1176 To make sure that this condition is verified for all possible pixel addresses, it is sufficient to check that:
1177 \begin{equation}
1178 \forall a \in \{0, 1, ... N_{l}-1\}, \left\lfloor \frac{a+H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1179 \end{equation}
1180 Indeed, by division by $N_{l}$ we have $a_{A} = k \cdot N_{l} + a$ with $0 \leq a \leq N_{l}-1$, which transforms equation~\ref{eq:noconflictwrap1} into:
1181 \begin{equation}
1182 k + \left\lfloor \frac{a}{N_{l}} \right\rfloor \not \equiv k + \left\lfloor \frac{a+H-1}{N_{l}} \right\rfloor \pmod{\frac{N_{c}}{N_{l}}}
1183 \end{equation}
1184 which leads easily to the result, considering that $\left\lfloor \frac{a}{N_{l}} \right\rfloor = 0$.
1185
1186 This can be further simplified:
1187 \begin{equation}
1188 \begin{cases}
1189 \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1190 1 + \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1191 \end{cases}
1192 \end{equation}
1193 \end{itemize}
1194
1195 \paragraph{Conflicts between channels 1 and 3 (or 2 and 4).}
1196 \begin{figure}[htp]
1197 \centering
1198 \includegraphics[height=55mm]{chdisp_hwrap.eps}
1199 \caption{Disposition of the channels within the texture, horizontal wrapping.}\label{fig:chdisphwrap}
1200 \end{figure}
1201 The separation between the channels' addresses can be:
1202 \begin{itemize}
1203 \item $H$ pixels (according to the equation~\ref{eq:fbadr}) in the general case (figure~\ref{fig:chdispcommon}). Using the same reasoning from above, we can deduce that it is sufficient to check that $H < N_{l}$ or:
1204 \begin{equation}
1205 \begin{cases}
1206 \left\lfloor \frac{H}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1207 1 + \left\lfloor \frac{H}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1208 \end{cases}
1209 \end{equation}
1210 \item $H \cdot (V-1)$ pixels if texture wrapping is enabled and the texture is sampled at one of its horizontal edges (figure~\ref{fig:chdisphwrap}). Again, it is sufficient to check that $H \cdot (V-1) < N_{l}$ or:
1211 \begin{equation}
1212 \begin{cases}
1213 \left\lfloor \frac{H \cdot (V-1)}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1214 1 + \left\lfloor \frac{H \cdot (V-1)}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1215 \end{cases}
1216 \end{equation}
1217 \end{itemize}
1218
1219 \paragraph{Conflicts between channels 1 and 4.}
1220 \begin{figure}[htp]
1221 \centering
1222 \includegraphics[height=55mm]{chdisp_hvwrap.eps}
1223 \caption{Disposition of the channels within the texture, horizontal and vertical wrapping.}\label{fig:chdisphvwrap}
1224 \end{figure}
1225 The channels' addresses can be separated by:
1226 \begin{itemize}
1227 \item $H + 1$ pixels (according to the equation~\ref{eq:fbadr}) in the general case (figure~\ref{fig:chdispcommon}). It is therefore sufficient to check that $H+1 < N_{l}$ or:
1228 \begin{equation}
1229 \begin{cases}
1230 \left\lfloor \frac{H+1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1231 1 + \left\lfloor \frac{H+1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1232 \end{cases}
1233 \end{equation}
1234 \item 1 pixel in case of vertical wrapping (figure~\ref{fig:chdispvwrap}). This cannot cause ICCCs.
1235 \item $H \cdot (V-1) - 1$ pixels in case of horizontal wrapping (figure~\ref{fig:chdisphwrap}). Similarly, we can check that $H \cdot (V-1) - 1 < N_{l}$ or:
1236 \begin{equation}
1237 \begin{cases}
1238 \left\lfloor \frac{H \cdot (V-1) - 1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1239 1 + \left\lfloor \frac{H \cdot (V-1) - 1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1240 \end{cases}
1241 \end{equation}
1242 \item $H \cdot V - 1$ in case of wrapping in both directions (figure~\ref{fig:chdisphvwrap}). We can check that $H \cdot V - 1 < N_{l}$ or:
1243 \begin{equation}
1244 \begin{cases}
1245 \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1246 1 + \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1247 \end{cases}
1248 \end{equation}
1249 \end{itemize}
1250
1251 \paragraph{Conflicts between channels 2 and 3.}
1252 Like above, we can check that $H-1 < N_{l}$ or:
1253 \begin{equation}
1254 \begin{cases}
1255 \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1256 1 + \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1257 \end{cases}
1258 \end{equation}
1259
1260 Furthermore, if texture wrapping is enabled, the differences between pixel addresses can become (resulting in similar conditions to check for):
1261 \begin{itemize}
1262 \item $2 \cdot H - 1$ (vertical wrapping, figure~\ref{fig:chdispvwrap}).
1263 \item $H \cdot (V - 1) + 1$ (horizontal wrapping, figure~\ref{fig:chdisphwrap}).
1264 \item $H \cdot (V - 2) + 1$ (wrapping in both directions, figure~\ref{fig:chdisphvwrap}).
1265 \end{itemize}
1266
1267 \paragraph{Summary.}
1268 To avoid inter-channel cache conflicts, when texture clamping is used, it is sufficient to check that (all equivalences are modulo $\frac{N_{c}}{N_{l}}$):
1269 \begin{equation}\label{eq:icccsum}
1270 \boxed{
1271 \begin{cases}
1272 H-1 < N_{l} & \textrm{ or } \begin{cases}
1273 \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \\
1274 1 + \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0
1275 \end{cases} \\
1276 H < N_{l} & \textrm{ or } \begin{cases}
1277 \left\lfloor \frac{H}{N_{l}} \right\rfloor \not \equiv 0 \\
1278 1 + \left\lfloor \frac{H}{N_{l}} \right\rfloor \not \equiv 0
1279 \end{cases} \\
1280 H+1 < N_{l} & \textrm{ or } \begin{cases}
1281 \left\lfloor \frac{H+1}{N_{l}} \right\rfloor \not \equiv 0 \\
1282 1 + \left\lfloor \frac{H+1}{N_{l}} \right\rfloor \not \equiv 0
1283 \end{cases}
1284 \end{cases}
1285 }
1286 \end{equation}
1287
1288 If texture wrapping is used, additional conditions appear:
1289 \begin{equation}\label{eq:icccsumwrap}
1290 \boxed{
1291 \begin{cases}
1292 H \cdot (V-1) - 1 < N_{l} & \textrm{ or } \begin{cases}
1293 \left\lfloor \frac{H \cdot (V-1) - 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1294 1 + \left\lfloor \frac{H \cdot (V-1) - 1}{N_{l}} \right\rfloor \not \equiv 0
1295 \end{cases} \\
1296 H \cdot (V-1) < N_{l} & \textrm{ or } \begin{cases}
1297 \left\lfloor \frac{H \cdot (V-1)}{N_{l}} \right\rfloor \not \equiv 0 \\
1298 1 + \left\lfloor \frac{H \cdot (V-1)}{N_{l}} \right\rfloor \not \equiv 0
1299 \end{cases} \\
1300 H \cdot (V-1) + 1 < N_{l} & \textrm{ or } \begin{cases}
1301 \left\lfloor \frac{H \cdot (V-1) + 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1302 1 + \left\lfloor \frac{H \cdot (V-1) + 1}{N_{l}} \right\rfloor \not \equiv 0
1303 \end{cases} \\
1304 H \cdot (V-2) + 1 < N_{l} & \textrm{ or } \begin{cases}
1305 \left\lfloor \frac{H \cdot (V-2) + 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1306 1 + \left\lfloor \frac{H \cdot (V-2) + 1}{N_{l}} \right\rfloor \not \equiv 0
1307 \end{cases} \\
1308 2 \cdot H - 1 < N_{l} & \textrm{ or } \begin{cases}
1309 \left\lfloor \frac{2 \cdot H - 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1310 1 + \left\lfloor \frac{2 \cdot H - 1}{N_{l}} \right\rfloor \not \equiv 0
1311 \end{cases} \\
1312 H \cdot V - 1 < N_{l} & \textrm{ or } \begin{cases}
1313 \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1314 1 + \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \not \equiv 0
1315 \end{cases}
1316 \end{cases}
1317 }
1318 \end{equation}
1319
1320 \subsubsection{Cache size}
1321 We must now determine an optimal size for the texel cache. The size must represent a compromise between hit rate (and, thus, performance) and costly utilization of on-chip RAM. Furthermore, it must be chosen so that inter-channel cache conflicts do not occur for our use cases.
1322
1323 To study the impact of the cache size on the hit rate, we simulated the complete Verilog code of texture mapping unit with different cache sizes. The CSR interface of the texture mapping unit (subsection~\ref{subsec:tmucsr}) supports eight registers that measure, for each channel, the number of requests\footnote{As outlined above, channels are only active (i.e. issue a cache request) when needed (i.e. when the interpolated texture coordinates are not integer). Channel 1 is always active and therefore makes as many accesses as there are pixels in the output picture. Its accesses are however still counted as a means to check that the texture mapping unit is operating correctly.} and how many of those requests hit the cache. Those registers are still present after logic synthesis, and can be used to validate the performance of the texel cache in the real system.\footnote{The reason why we performed the tests using Verilog simulations instead of the real FPGA-based system is because logic synthesis --- needed for each tested cache size --- takes a long time, and some cache configurations may cause resource shortages, timing problems or even Xst synthesizer bugs that would need to be manually addressed.}
1324
1325 The source and destination images have a resolution of 512x512 pixels, and are tesselated with 16x16 rectangles forming a 32x32 mesh --- which matches the configuration used for distortions by the renderer program. Different sets of texture coordinates were used at each vertex, according to table~\ref{tab:tcsets}. Texture coordinates are multiplied by 64 to perform the conversion of integers into the fixed point format used throughout the linear interpolation process (see subsection~\ref{subsec:bilfpformat}). $x$ and $y$ refer to the indices of the vertex in the mesh. Texture wrapping was enabled, as it puts more load on the cache than texture clamping.
1326
1327 The sets were chosen for the following reasons:
1328 \begin{itemize}
1329 \item \textit{copy} does not introduce any distortion and is meant to test the performance of the TMU as a blitter, that could be used e.g. for GUI acceleration. It is also a very simple case that verifies the consistency of the results.
1330 \item \textit{zoomin} scales up the picture. This tests the TMU in a favorable case: as the amount of zoom is important, the texels are swept across slower than output pixels are drawn. This is expected to generate a lot of cache hits.
1331 \item \textit{zoomout} scales down and repeats the picture. This is a detrimental case: the texels are swept across faster than the output pixel are drawn, and some values from the cache lines read from memory will have to be discarded. This is expected to generate a lot of cache misses.
1332 \item \textit{rotozoom} slightly scales down and rotates the picture. This is an intermediate case that reflects what MilkDrop typically does: rotation and slight scale-down are common preset effects.
1333 \end{itemize}
1334
1335 \begin{table}
1336 \centering
1337 \begin{tabularx}{13cm}{|c|c|X|X|}
1338 \hline
1339 \textbf{Set name} & \textbf{Output picture} & \textbf{X} & \textbf{Y} \\
1340 \hline
1341 copy & Figure~\ref{fig:tmuoutcopy} & $x \cdot 16 \cdot 64$ & $y \cdot 16 \cdot 64$ \\
1342 \hline
1343 zoomin & Figure~\ref{fig:tmuoutzoomin} & $x \cdot 10 \cdot 64$ & $y \cdot 10 \cdot 64$ \\
1344 \hline
1345 zoomout & Figure~\ref{fig:tmuoutzoomout} & $x \cdot 40 \cdot 64$ & $y \cdot 40 \cdot 64$ \\
1346 \hline
1347 rotozoom & Figure~\ref{fig:tmuoutrotozoom} & $(x\cdot16-256)\cdot67 - (y\cdot16-256)\cdot28+256\cdot64$ & $(x\cdot16-256)\cdot28 + (y\cdot16-256)\cdot67+256\cdot64$ \\
1348 \hline
1349 \end{tabularx}
1350 \caption{Texture coordinate sets used for benchmarking the texel cache.}\label{tab:tcsets}
1351 \end{table}
1352
1353 \begin{figure}[htp]
1354 \centering
1355 \includegraphics[height=85mm]{tmuout_copy.eps}
1356 \caption{TMU output picture for the ``copy'' set (original picture).}
1357 \label{fig:tmuoutcopy}
1358 \end{figure}
1359
1360 \begin{figure}[htp]
1361 \centering
1362 \includegraphics[height=85mm]{tmuout_zoomin.eps}
1363 \caption{TMU output picture for the ``zoomin'' set.}
1364 \label{fig:tmuoutzoomin}
1365 \end{figure}
1366
1367 \begin{figure}[htp]
1368 \centering
1369 \includegraphics[height=85mm]{tmuout_zoomout.eps}
1370 \caption{TMU output picture for the ``zoomout'' set.}
1371 \label{fig:tmuoutzoomout}
1372 \end{figure}
1373
1374 \begin{figure}[htp]
1375 \centering
1376 \includegraphics[height=85mm]{tmuout_rotozoom.eps}
1377 \caption{TMU output picture for the ``rotozoom'' set.}
1378 \label{fig:tmuoutrotozoom}
1379 \end{figure}
1380
1381 The length of the cache line is set to the length of a FML burst in the SoC (4 words of 64 bits each) for simplicity of the design.
1382
1383 Simulations were carried out using the free GPL Cver Verilog simulator~\cite{gplcver}. To visually inspect the results of the distortions stemming from each set of texture coordinates, the simulation reads and writes input and output picture files thanks to a Verilog VPI~\cite{vpi} plug-in.\footnote{This was also part of the usual test bench used to debug the Verilog implementation of the texture mapping unit.} A typical simulation trace is reproduced in figure~\ref{fig:tmusimtrace}. Even though GPL Cver is relatively slow\footnote{Its runtime is between one and three minutes on a Intel Core 2 Duo 2.5GHz machine.} to carry out such a complex simulation, it produced consistent results, which supports the idea that it is, in many cases, a viable alternative to proprietary and expensive simulators commonly taught in university courses.
1384
1385 \begin{figure}
1386 \centering
1387 \begin{boxedminipage}{13cm}
1388 \begin{verbatim}
1389 $ make TB=tb_tmu2.v
1390 cver +loadvpi=./vpi_images.so:vpi_register tb_tmu2.v
1391 (...)
1392 GPLCVER_2.12a of 05/16/07 (Linux-elf).
1393 Copyright (c) 1991-2007 Pragmatic C Software Corp.
1394   All Rights reserved.  Licensed under the GNU General Public
1395   License (GPL).
1396   See the 'COPYING' file for details.  NO WARRANTY provided.
1397 Today is Tue May  4 14:46:22 2010.
1398 PLI Image I/O functions registered
1399 Compiling source file "tb_tmu2.v"
1400 Compiling source file "../rtl/tmu2_adrgen.v"
1401 (...)
1402
1403 Opening input picture...
1404 Configuring TMU...
1405 CSR write: 0000002c=01000000
1406 CSR write: 00000004=00000020
1407 (...)
1408 CSR write: 00000044=00000010
1409 CSR write: 00000048=0000003f
1410 Starting TMU...
1411 CSR write: 00000000=00000001
1412 Received DONE IRQ from TMU!
1413 Gathering texel cache statistics...
1414 CSR read : 00000050=00040000
1415 CSR read : 00000054=0003c000
1416 (...)
1417 CSR read : 00000068=00000000
1418 CSR read : 0000006c=00000000
1419 Channel A:      245760 /      262144 hits (93.750000 %)
1420 Channel B:           0 /           0 hits (nan %)
1421 Channel C:           0 /           0 hits (nan %)
1422 Channel D:           0 /           0 hits (nan %)
1423 GLOBAL   :      245760 /      262144 hits (93.750000 %)
1424 Writing output picture...
1425 All done!
1426 Halted at location **tb_tmu2.v(367) time 4585546 from call
1427 to $finish.
1428   There were 0 error(s), 32 warning(s), and 402 inform(s).
1429 \end{verbatim}
1430 \end{boxedminipage}
1431 \caption{Typical TMU simulation trace (excerpt).}
1432 \label{fig:tmusimtrace}
1433 \end{figure}
1434
1435 Results are reported in table~\ref{tab:tcresults} and figure~\ref{fig:tcresultsgraph}. Only the \textit{global} hit rate is reported, which is computed as the global number of hits over the global number of accesses. The global number of hits (respectively  accesses) is the sum of the number of hits (respectively accesses) for all channels. The reported cache size is the size of the data store only (not counting the tag memory).
1436
1437 \begin{table}
1438 \centering
1439 \begin{tabular}{|c|c|c|c|c|}
1440 \hline
1441 \textbf{Cache size} & \textbf{copy} & \textbf{zoomin} & \textbf{zoomout} & \textbf{rotozoom} \\
1442 \hline
1443 2KB & 93.75 \% & 98.08 \% & 83.33 \% & 73.06 \% \\
1444 \hline
1445 4KB & 93.75 \% & 98.08 \% & 83.33 \% & 82.94 \% \\
1446 \hline
1447 8KB & 93.75 \% & 98.62 \% & 83.33 \% & 93.73 \% \\
1448 \hline
1449 16KB & 93.75 \% & 99.27 \% & 86.94 \% & 95.74 \% \\
1450 \hline
1451 32KB & 93.75 \% & 99.27 \% & 91.44 \% & 96.02 \% \\
1452 \hline
1453 64KB & 93.75 \% & 99.27 \% & 94.14 \% & 96.02 \% \\
1454 \hline
1455 128KB & 93.75 \% & 99.27 \% & 94.14 \% & 96.15 \% \\
1456 \hline
1457 \end{tabular}
1458 \caption{Hit rates for each set of texture coordinates and different cache sizes.}\label{tab:tcresults}
1459 \end{table}
1460
1461 \begin{figure}[htp]
1462 \centering
1463 \includegraphics[height=95mm]{tcresultsgraph.eps}
1464 \caption{Hit rates versus texel cache size. The X axis (cache size) uses a logarithmic scale.}
1465 \label{fig:tcresultsgraph}
1466 \end{figure}
1467
1468 Before we go on choosing a texel cache size, a few comments on these results can be made.
1469
1470 First, for the ``copy'' set, the hit rate remains at a constant 93.75 \%. This is expected and supports the validity of the results. Indeed, the texture mapping unit is copying rectangles whose horizontal size is the length in pixels of a cache line (4 words of 64-bit each yields 16 pixels of 16 bits each). In our tests, the texture frame buffer was aligned to the beginning of a cache line and 512 (the horizontal texture size) is a multiple of the cache line length in pixels, therefore each horizontal line in a rectangle corresponds to a cache line. Each texture pixel is read exactly once (channels 2, 3 and 4 are idle as the interpolated texture coordinates are always integer). What happens is that, for each horizontal line in each rectangle, the first texel is read and misses the cache. Then, the next 15 texels in the line are immediately read and hit the cache. This indeed yields a cache hit rate of $\frac{15}{16} = 0.9375$.
1471
1472 A result more surprising at first sight is that for the ``zoomout'' set, which is supposed to be the worst case, the cache hit rate is low --- as expected --- and increases, until it slightly exceeds the hit rate for the ``copy'' set for cache sizes of 64KB and above.
1473
1474 This has to do with the fact that the texture mapping unit draws the rectangles in the same order as frame buffers are scanned (from left to right and top to bottom). When the cache reaches 64KB, it is able to memorize a full band of texels that is more than 48 pixels high ($512\cdot48\cdot2 = 49152 < 65536$) which contains more than all the texels needed to draw a full line of rectangles (16 pixels high) in the output picture. Since the output picture repeats the texture, the repetition generates cache hits that are not present with the ``copy'' set.
1475
1476 As for choosing a texel cache size, we went for a 32KB cache. There is no significant performance improvement with using a larger cache except for the ``zoomout'' set for which there is a slight increase in the hit rate between 32KB and 64KB. Since the ``zoomout'' set is a worst-case scenario seldom found in practice (MilkDrop usually zooms out by factors much less than the one we used, resulting in fewer cache misses), we felt it was not worth doubling the cache size to improve its performance.
1477
1478 We also need to check that this cache size cannot cause inter-channel cache conflicts (ICCCs). The cache line size is 32 bytes, thus, the cache line length in 16bpp pixels is $N_{l} = 16$ and the cache holds $\frac{N_{c}}{N_{l}}=1024$ lines. The texture mapping unit is operated with 512x512 textures and texture wrapping is enabled.
1479
1480 With these parameters, all the conditions of equations \ref{eq:icccsum} and \ref{eq:icccsumwrap} are verified, except one: we have $1 + \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \equiv 0$, which means that there can be inter-channel cache conflicts between channels 1 and 4 due to wrapping. Without additional hypotheses, this can only be solved by increasing the cache size to at least 1MB, which would be very expensive.
1481
1482 Fortunately, there is a cheaper solution. What we actually need to verify is this condition, obtained in the same way as equation~\ref{eq:noconflictwrap1}:
1483 \begin{equation}
1484 \left\lfloor \frac{a_{A}}{N_{l}} \right\rfloor \not \equiv \left\lfloor \frac{a_{A}+H \cdot V-1}{N_{l}} \right\rfloor \pmod{\frac{N_{c}}{N_{l}}}
1485 \end{equation}
1486
1487 We \textit{add} the hypothese that the frame buffer address is a multiple of the cache line length, which we can easily achieve by imposing alignment requirements to the software toolchain. Without loss of generality, we suppose that $a_{A}$ is the address of channel 4, which is equal to the address of the frame buffer in the case creating the problem (figure~\ref{fig:chdisphvwrap}). $\frac{a_{A}}{N_{l}}$ is therefore integer, and the only condition that implies the absence of conflict between channels 1 and 4 becomes:
1488 \begin{equation}
1489 \left\lfloor \frac{H \cdot V-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1490 \end{equation}
1491 This condition is verified. So, ICCCs will always be avoided with a 32KB texel cache if we make sure that the 512x512 texture is aligned to a 32-byte boundary.
1492
1493 \subsection{Bilinear filter}
1494 The bilinear filter is a straightforward arithmetic circuit that implements the equation~\ref{eq:bfilter} with five pipeline sub-stages.
1495
1496 \subsection{Write buffer}
1497 The write buffer is in charge of gathering the final pixels produced by the algorithm, assemble them into FML bursts and write them to the memory.
1498
1499 The write buffer has enough memory capacity to store two bursts on-chip. This storage space is used for a ``double buffering'' technique: while the first burst buffer receives pixels from the pipeline, the other buffer can transmit data to the memory controller. Bursts can be complete, which means that all data in them is valid, or incomplete, which means that the write buffer has not received a value for all the pixels within the burst but still needs to move the partial burst data it has off-chip because it does not have space to store it. Incomplete bursts are performed using the data mask (DM) signals of FML that prevent some bytes from being written to the memory during the burst. Incomplete bursts should be avoided as they waste memory bandwidth and reduce performance.
1500
1501 This small amount of on-chip memory is enough to perform well. Indeed, the algorithm scans the rectangles one by one horizontally and then vertically (figure~\ref{fig:rectinter}) and consecutive pixels on the same horizontal line are contiguous in memory (equation~\ref{eq:fbadr}). Thus, if the destination frame buffer is aligned to the start of a FML burst and if the horizontal size of the rectangles is a multiple of the number of pixels in a FML burst, the burst buffers will be used very efficiently, with complete bursts only. This is the recommended mode of operation for the texture mapping unit.
1502
1503 Under this assumption, what limits the throughput of the write buffer is the time it takes to empty the second burst buffer into the memory. This time is equal to the memory write access time plus the length of the FML burst.
1504
1505 In the equations that follow, these symbols are used:
1506 \begin{itemize}
1507 \item $f$ is the system clock frequency in Hz.
1508 \item $w$ is the width of a FML word in bits.
1509 \item $n$ is the FML burst length.
1510 \item $\Delta_{w}$ is the memory write access time.
1511 \item $d$ is the number of bits per pixel.
1512 \item $T$ is the throughput of the write buffer, in pixels per second.
1513 \end{itemize}
1514
1515 We therefore have:
1516 \begin{equation}
1517 T = \frac{f \cdot n \cdot w}{d \cdot (\Delta_{w} + n)}
1518 \end{equation}
1519
1520 Thus, the write buffer can achieve a throughput of one pixel per clock cycle ($T = f$) if the memory write access time verifies:
1521 \begin{equation}
1522 \Delta_{w} \leq \frac{n \cdot w}{d} - n
1523 \end{equation}
1524
1525 In Milkymist, the color format uses 16 bits per pixel and the FML bus is based on bursts of four 64-bit words, which leads to the throughput plot of figure~\ref{fig:thwbufperf}.\footnote{In our implementation, the throughput is also limited to a maximum of 100 megapixels per second because of the width of the write buffer input port.} The write buffer can tolerate write latencies of up to 12 cycles while maintaining an excellent performance of one pixel per clock cycle, which seems achievable even when taking into account the delays due to bus arbitration. Beyond this point, performance drops.
1526
1527 \begin{figure}[htp]
1528 \centering
1529 \includegraphics[height=95mm]{thwbufperf.eps}
1530 \caption{Theoretical write buffer throughput versus memory write access time.}
1531 \label{fig:thwbufperf}
1532 \end{figure}
1533
1534 \subsection{Control interface}
1535 \label{subsec:tmucsr}
1536 The texture mapping unit is completely under software control thanks to a CSR interface through which the CPU can configure and control it using a set of configuration and status registers. The texture mapping unit has one interrupt line to signal completion of the process to the CPU.
1537
1538 \section{Extra features}
1539 Beyond this basic principle of operation, the texture mapping unit supports several features which are implemented as additional pipeline stages (not shown in figure~\ref{fig:tmublock}):
1540 \begin{itemize}
1541 \item Fade to black. To implement the ``decay'' effect of MilkDrop, the output picture can be darkened by multiplying all its color components by a 6-bit fixed point number between 0 and 1.
1542 \item Chroma key. Texels of a given color can be ignored (not drawn in the output frame buffer). This is not used in normal rendering, but makes it possible to draw quickly text or symbols with transparent areas on the screen.
1543 \item Semi-transparency (alpha blending). The output can be made semi-transparent with 64 transparency levels. This is accomplished by reading the destination picture, mixing each pixel with the output of the texture mapping (by computing a weighted average) and writing the result back to memory. If transparency is not desired, the texture mapping unit skips reading the destination picture in order to use less memory bandwidth and avoid blocking on unneeded memory references.
1544 \end{itemize}
1545
1546 \section{Implementation results}
1547 We were unable to implement the planned 32KB texel cache in the XC4VLX25 FPGA of our ML401 development board, because the complete SoC with such a cache exceeds the on-chip SRAM capacity of the FPGA. Therefore, for these experiments, we had to use a 16KB cache instead. This issue should be resolved easily in the future, as our final board (chapter~\ref{ch:conclusion}) will have an FPGA with much more on-chip memory.
1548
1549 We wanted to validate the performance of our texture mapping unit (TMU) design, measured in megapixels per second at the output (also called \textit{fill rate}). Since it is a memory-bound process (subsection~\ref{subsec:tmustrategy}), it is relevant to examine its performance for different values of the texel cache hit rate.
1550
1551 To do so, we varied the texel cache hit rate by making the TMU zoom a picture at different levels. We proceeded with a texture size of 512x512 and an output picture of 640x480. The vertex mesh had a resolution of 32x32, and, to implement the different zoom levels, the vertex coordinates were $(z \cdot x, z \cdot y)$ with $z$ varying between 0 and 2047. Each measurement was done twice to reduce the risk of errors and transients (CPU interrupts, DRAM refreshes, etc.), yielding 4096 points which are plotted in figure~\ref{fig:tmuresult}. The measurements were done programmatically by a software routine running on the system-on-chip itself. The video output was enabled during the process (and showing the result of the texture mapping), running in the standard VGA mode of 640x480 at 60Hz and putting a background load of approximately 300 Mbit/s on the memory system for scanning the frame buffer.
1552
1553 \begin{figure}[htp]
1554 \centering
1555 \includegraphics[height=75mm]{tmuresult.eps}
1556 \caption{Measured TMU performance versus global texel cache hit rate.}
1557 \label{fig:tmuresult}
1558 \end{figure}
1559
1560 The plot underlines the importance of the memory subsystem in a performance-driven texture mapping unit design. Indeed, performance drops sharply as soon as many off-chip memory references begin to be made (especially between hit rates of 100\% and 98.5\%). Our texture mapping unit is unable to meet its initial performance goal of 31 megapixels per second for hit rates below approximately 96\%. Prefetching would be a good way to improve this result~\cite{tmprefetch}, but it comes at the cost of an increased hardware complexity.
1561
1562 However, our design still appears suitable for the application of rendering MilkDrop-like patches with all the options enabled (i.e. in the worst case) at VGA resolution (640x480). Indeed, this would involve:
1563 \begin{enumerate}
1564 \item Distortion of a 512x512 texture to a 512x512 texture. This is represented by the ``rotozoom'' set of vertex coordinates (table~\ref{tab:tcsets}) whose resulting cache hit rate is 95.74 \% (table~\ref{tab:tcresults}). The fill rate is therefore approximately 30 megapixels per second (figure~\ref{fig:tmuresult}). The time taken by this process is thus $\frac{512 \cdot 512}{30 \cdot 10^{6}}=8.7\unit{ms}$.
1565 \item Inclusion of a live video frame into the texture.\footnote{We are --- very optimistically --- neglecting the time it takes to read the output picture when alpha blending is enabled.} We assume the input video frame to be 720x288 (we are using \textit{bob deinterlacing}, i.e. line doubling of the interlaced video frames) and the target rectangle in the texture to be 360x288. This is represented by the ``zoomout'' set with a cache hit rate of 86.94 \% yielding a fill rate of very approximately 15 megapixels per second. The time taken by this process is $\frac{360 \cdot 288}{15 \cdot 10^{6}}=6.9\unit{ms}$.
1566 \item Zooming of the 512x512 texture to 640x480 resolution, done twice (once for the normal picture and once for video echo\footnote{Again neglecting the extra delay due to alpha blending.}). This is represented by the ``zoomin'' set of vertex coordinates. The texel hit rate is estimated at 99.27\%, and the fill rate at 55 megapixels per second. The time taken is estimated to be $2 \cdot \frac{640 \cdot 480}{55 \cdot 10^{6}}=11.2\unit{ms}$.
1567 \end{enumerate}
1568
1569 The total time is $26.8\unit{ms}$, which corresponds to 37 frames per second. This is more than enough to achieve a smooth video animation.
1570
1571 \chapter{Floating point coprocessor}
1572 \label{ch:pfpu}
1573 \section{Purpose}
1574 \label{sec:pfpupurpose}
1575 Patches define floating-point equations that are evaluated at each vertex (subsection~\ref{subsec:mdprinciple}). Furthermore, per-frame variables such as \verb!zoom!, \verb!rot! or \verb!cx! alter the texture coordinates at each vertex, and correspond to built-in per-vertex equations.
1576
1577 We would like to be able to generate a mesh of up to 64x64 vertices at 30 frames per second, that is to say, compute the X and Y texture coordinates for 122880 vertices each second. With a 100MHz system clock, we have, on average, 813 cycles to fully process each vertex. We want to be able to do 470 basic floating point operations (addition, subtraction, multiplication) per vertex.\footnote{The MilkDrop patches contain many other functions. We count divisions and square roots as 15 basic floating point operations and trigonometric functions as 10. We want a patch to be able to do, per vertex, 150 base operations, 8 divisions/square root extractions, and 20 trigonometric operations. This yields the estimate of $150+8\cdot15+20\cdot10=470$ basic operations.} This means we have, on average, 1.73 cycles to perform each basic floating point operation.
1578
1579 This rules out any software-based implementation. Even assuming a favorable case where patches are compiled (not interpreted) and the LatticeMico32 ISA (section~\ref{sec:mico32}) equipped with a traditional floating point unit, each basic floating point operation would take approximately 5 cycles at least.\footnote{FPGAs are unlikely to compute the totality of a floating point operation in less than 50ns, which is 5 cycles at 100MHz. Since LatticeMico32 uses a fixed-length in-order pipeline, the CPU would need to be stalled during those cycles.} Even at 100\% CPU utilization, a software implementation would be 3 times too slow!
1580
1581 We have therefore designed and implemented a coprocessor for those computations, called PFPU (Programmable Floating Point Unit).
1582
1583 \section{Forms of parallelism}
1584 We need a parallel implementation to solve the problem of performance. Two approaches can be thought of: \textit{vertex-level parallelism} and \textit{instruction-level parallelism}.
1585
1586 Vertex-level parallelism is a very simple concept. Since the vertices are independent, the idea is to process several at once. The problem with this approach is that a significant amount of (typically on-chip) memory is needed to store all the intermediate results generated by this technique.
1587
1588 Instruction-level parallelism consists in carrying out in parallel two or more independent computations \textit{for the same vertex}. With this approach, the vertices can be computed one by one, which reduces the required amount of on-chip storage for intermediate results and simplifies the memory access subsystem (as it does not have to handle accesses to different vertices stemming from the same PFPU program).
1589
1590 The two approaches are not mutually exclusive. A hybrid solution can consist in starting with instruction-level parallelism, and then try to schedule more vertices into the same program until the on-chip memory capacity is exceeded.
1591
1592 We do not want such a complex solution to begin with, so we are going with instruction-level parallelism only. If more performance is needed, the addition of vertex-level parallelism can be tried at the expense of relatively small modifications to the hardware.
1593
1594 \section{Hardware architecture}
1595 \subsection{Overview}
1596 A fully software-based extraction of instruction-level parallelism was chosen for several reasons:
1597 \begin{itemize}
1598 \item Hardware-based extraction is more costly in terms of resources and more difficult to develop.
1599 \item In terms of performance, choosing an hardware-based extraction only pays off compared to a software-based solution when some delays can only be determined at run-time (for example, the memory references). In our case, computations last for approximately 800 cycles and end up with a memory write phase that takes approximately 10 cycles, so the memory delays are negligible and all the other processes (arithmetic pipelines and register writes) have known latencies. Furthermore, we only write to the memory, which means that we can even use a write queue to completely hide the memory write latency.
1600 \item A software-based instruction scheduler can have a large instruction window, and thus extract more parallelism than an hardware solution could.
1601 \end{itemize}
1602
1603 This static scheduling technique makes the floating point coprocessor close to a VLIW (Very Long Instruction Word) processor --- even though its instruction words are, in fact, not particularly long, as the design is very simple (only one operation is issued per instruction, and jumps are not supported). The architecture we designed is outlined in figure~\ref{fig:pfpuarch}.
1604
1605 \begin{figure}[htp]
1606 \centering
1607 \includegraphics[height=100mm]{pfpu_architecture.eps}
1608 \caption{Hardware architecture of the floating point coprocessor.}
1609 \label{fig:pfpuarch}
1610 \end{figure}
1611
1612 \subsection{Instruction set}
1613 The 25-bit PFPU instruction format is given in table~\ref{tab:pfpuinst}. The PFPU executes one such instruction per clock cycle.
1614
1615 \begin{table}
1616 \centering
1617 \begin{tabular}{|l|l|l|l|l|}
1618 \hline
1619 \textbf{Parameter} & Operand A & Operand B & Opcode & Destination \\
1620 \hline
1621 \textbf{Length} & 7 & 7 & 4 & 7 \\
1622 \hline
1623 \textbf{Bits} & \verb!24..18! & \verb!17..11! & \verb!10..7! & \verb!7..0! \\
1624 \hline
1625 \end{tabular}
1626 \caption{PFPU instruction format.}\label{tab:pfpuinst}
1627 \end{table}
1628
1629 An instruction can be split into two parts: the \textit{issue} part, made of the two operand fields and the opcode field, and the \textit{commit} part, made of the destination field. At each cycle, the issue part can fetch two operands from the register file and pushes them into one of the several arithmetic pipelines forming the ALU (Arithmetic and Logic Unit), selected by the ``opcode'' field. At the same time, the commit part can fetch one result from the ALU (stemming from a previously issued operation that has just finished) and write it back to the register file.
1630
1631 The PFPU program must be written so that all data dependencies are satisfied and only up to one instruction finishes at any given clock cycle (having more than one would create a conflict as there is only a single write port on the register file).
1632
1633 A special instruction is used to write the final result to the memory. It writes the two operands in a format that can be directly read as a texture coordinate by the texture mapping unit (chapter~\ref{ch:tmu}). Upon the execution of this instruction, the program for the current vertex is terminated and run again for the next, until all vertices have been processed.
1634
1635 \subsection{Instruction RAM}
1636 The instruction RAM belongs on-chip for two simple reasons:
1637 \begin{itemize}
1638 \item it is small: it must only contain hundreds of instructions (the program for one vertex), so its capacity is only a few kilobytes.
1639 \item it transfers a large amount of data: one 25-bit instruction on each clock cycle at 100MHz yields a bandwidth of 2.5Gbps.
1640 \end{itemize}
1641 There are no jumps or loop structures (for each vertex, the program is always executed linearly), so it does not make sense to replace it with a DRAM-backed cache.
1642
1643 \subsection{ALU}
1644 \subsubsection{Overview}
1645 The Arithmetic and Logic Unit (ALU) uses 32-bit floats using the same representation as specified by the IEEE 754 standard. This gives enough precision for graphics operations.
1646
1647 The major pipelines of the ALU are listed below.
1648
1649 \subsubsection{Basic operations}
1650 The unit has pipelines that perform common operations: addition, subtraction, multiplication, absolute value and conversion between floats and two's complement integers.
1651
1652 \subsubsection{Inverse square root approximation}
1653 The ALU can compute an approximate of the inverse square root of a floating point number using the Quake III method~\cite{invsqrt}. The ALU only performs the integer operation \verb!0x5f3759df - (i >> 1)!, the subsequent floating point Newton-Raphson iterations needing to be done with additional instructions. This is described in subsection~\ref{subsec:fpvm}.
1654
1655 \subsubsection{Sine and cosine}
1656 Sine and cosine are implemented with a look-up table and some logic that exploits the evenness and periodicity of those functions to reduce the size of the look-up table. To compute the sine or cosine of a floating point number, additional instructions need to be generated to convert this number into an integer suitable for indexing the look-up table.
1657
1658 \subsubsection{Comparisons}
1659 The ALU can test the equality of two floating point numbers and test if one is greater than the other, using two separate opcodes. The result of these operations is 0.0 or 1.0, which can be used as a floating point number in other computations or written to register R2 to implement a conditional statement.
1660
1661 \subsubsection{Conditional statements}
1662 Conditional statements (if... then... else...) are relatively uncommon in MilkDrop patches, so a low area and straightforward --- but slow --- implementation was chosen. A special opcode enables a multiplexer that switches between operand A and B and returns the result. The multiplexer is controlled by the register R2, the value of this register being null or non-null selects one or the other input.
1663
1664 Thus, to implement a conditional statement, the PFPU would need to compute both of its branches and store their values in registers (including the branch that is not taken), evaluate the condition and store its value in R2 and finally execute an \verb!IF! operation.
1665
1666 \section{Run-time compiler}
1667 \label{sec:pfpucomp}
1668 Equations from the patches need to be compiled and scheduled before they can be evaluated by the programmable floating point unit (PFPU). These operations take place on the CPU core of the SoC (section~\ref{sec:mico32}).
1669
1670 \subsection{Compilation into virtual machine instructions}
1671 \label{subsec:fpvm}
1672 The first step in this process is the compilation proper, i.e. parsing the equations and generating instructions for the so-called \textit{floating point virtual machine} (FPVM). This virtual machine has the following properties:
1673 \begin{itemize}
1674 \item It has the same operations and opcodes as the PFPU.
1675 \item Instructions complete and write their result to the register file in one cycle.
1676 \item The number of registers is unlimited.\footnote{Actually, it is limited to $2^{32}$ in our implementation, which can be considered unlimited for our purposes.}
1677 \end{itemize}
1678
1679 The compiler employs the fact that the number of registers is unlimited to generate a code that is free from false and output dependencies\footnote{Almost. In order to interface in a simple way the code with the ``outside world'' (subsection~\ref{subsec:constparam}), the compiler can be constrained to allocate a given variable to a given register. Depending on how the variable is used, false and output dependencies might actually appear. The scheduler therefore has to check for write-after-read (WAR) and write-after-write (WAW) hazards. Furthermore, conditional statements can cause WAR and WAW hazards around the R2 register, since the IF operation can only use R2 to get the condition value from. However, since all these hazards are extremely rare, they can be resolved by waiting (instead of register renaming) without a significant impact on performance.} (by allocating a new register for each result) in order to simplify the task of the scheduler (subsection~\ref{subsec:vliwsched}), which does not have to perform register renaming to create more opportunities for out-of-order execution.
1680
1681 Because of the limited functionality of the operations supported by the FPVM (and the PFPU), some ``compound'' functions need to be implemented with several instructions. They are detailed below.
1682
1683 \subsubsection{Sine and cosine}
1684 The sine and cosine instructions expect an integer angle expressed in $\frac{1}{8192}$ turns. Angles outside of the range $[0, 8191]$ are correctly processed (i.e. multiples of 8192 are added or subtracted, by simply ignoring the most significant bits of the input). Therefore, to return the sine or cosine of a floating point angle expressed in radians, the compiler needs to generate three instructions:
1685 \begin{enumerate}
1686 \item Multiply by $\frac{8192}{2 \cdot \pi}$.
1687 \item Convert to integer.
1688 \item Look-up the sine or cosine value.
1689 \end{enumerate}
1690
1691 \subsubsection{Inverse square root}
1692 \begin{figure}
1693 \centering
1694 \begin{boxedminipage}{13cm}
1695 \begin{math}
1696 y \leftarrow \textrm{cast\_to\_float}(\textrm{0x5f3759df} - (\textrm{cast\_to\_integer}(x) >> 1)) \\
1697 y \leftarrow y \cdot (1.5 - 0.5 \cdot x \cdot y \cdot y)\textrm{ // first Newton-Raphson iteration} \\
1698 y \leftarrow y \cdot (1.5 - 0.5 \cdot x \cdot y \cdot y)\textrm{ // second iteration}
1699 \end{math}
1700 \end{boxedminipage}
1701 \caption{Fast inverse square root algorithm.}
1702 \label{fig:invsqrt}
1703 \end{figure}
1704
1705 The inverse square root ($\frac{1}{\sqrt{x}}$) is implemented using the Quake III algorithm~\cite{invsqrt}, reproduced in figure~\ref{fig:invsqrt} with the two Newton-Raphson iterations for improved precision. The input of the algorithm is $x$ and the output $y$. The cast\_to\_float function returns the float whose binary representation as specified by IEEE 754 is the same as that of the integer parameter. The cast\_to\_integer function performs the opposite operation. They allow the bit twiddling of the numbers in order to produce an initial approximation of the result, which is then refined using the Newton-Raphson method. This is the core idea of the algorithm.
1706
1707 The algorithm produces an approximate value of the inverse square root, with a worst case relative precision of $4.66 \cdot 10^{-6}$ over all floating point values when the two Newton-Raphson iterations are used (according to \cite{invsqrt}).
1708
1709 Only a special instruction for performing the first approximation step is provided. The compiler must therefore generate extra multiplication and subtraction instructions for the two iteration steps.
1710
1711 \subsubsection{Square root}
1712 The square root is implemented using inverse square root with an additional multiplication, according to $\sqrt{x} = x \cdot \frac{1}{\sqrt{x}}$. The relative precision stays approximately\footnote{Not counting the loss of precision incurred by truncating the mantissa of the floating point multiplication result.} the same.
1713
1714 \subsubsection{Inverse and division}
1715 The inverse of positive numbers is implemented by squaring the inverse square root: $\frac{1}{x} = \frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}}$. The relative precision obtained is approximately $9.32 \cdot 10^{-6}$.
1716
1717 Divisions of arbitrary numbers are performed by first transferring the sign of the denominator to the numerator, and then multiplying it by the inverse (obtained as above) of the denominator: $\frac{a}{b} = \textrm{sign}(b) \cdot a \cdot \frac{1}{\sqrt{|b|}} \cdot \frac{1}{\sqrt{|b|}}$. The relative precision is still approximately $9.32 \cdot 10^{-6}$.
1718
1719 The compiler needs to generate many instructions to implement a division, which makes it a rather slow process. However, with this method, very little hardware needs to be added to the PFPU: only support for transferring the sign to the numerator needs to be implemented.
1720
1721 \subsection{Scheduling}
1722 \label{subsec:vliwsched}
1723 Once the complete code is available as FPVM instructions, the next step is to map these instructions to the PFPU and schedule them.
1724
1725 Our scheduling algorithm proceeds cycle by cycle. At each PFPU cycle (which corresponds to a PFPU instruction), it searches the complete set of FPVM instructions waiting to be scheduled for one that meets the following four conditions:
1726 \begin{enumerate}
1727 \item No read-after-write (RAW) hazard. The operands for the instruction to be scheduled must have been stored into the register file of the PFPU, otherwise, the instruction is not scheduled.
1728 \item No write-after-write (WAW) hazard. If there is a previous uncompleted instruction that writes to the same register as the instruction to be scheduled, the instruction is not scheduled.
1729 \item No write-after-read (WAR) hazard. If there is a previous unscheduled FPVM instruction that reads the register that the instruction to be scheduled modifies, the instruction is not scheduled.
1730 \item No output conflict. The instruction to be scheduled must not complete at the same cycle as another previously scheduled instruction.
1731 \end{enumerate}
1732 If an instruction is found, the FPVM registers of its operands are translated to PFPU registers, a PFPU register is allocated for its output register so that further instructions needing the result can read it, and the instruction is written to the PFPU program. If no further instruction needs to read the operands of the instruction just scheduled, the registers are deallocated in order to save the limited PFPU register space (unless they are bound to a constant or user variable, see subsection \ref{subsec:constparam}). The algorithm then proceeds to the next cycle.
1733
1734 It can be noted that the handling of WAW and WAR hazards is zealous, as some hazards detected by the algorithm may actually not be present because of the pipeline delays. Since those hazards are infrequent, this approach does not have a large impact on the performance but simplifies the algorithm.
1735
1736 Several instructions can sometimes meet the conditions to be schedulable at the same cycle. In this case, the algorithm chooses the first one to appear in the FPVM instruction flow. This \textit{greedy} approach can certainly be optimized, though no effort has been made in this direction.
1737
1738 \subsection{Constants and user variables}
1739 \label{subsec:constparam}
1740 Constant values are assigned a specific register by the compiler, that needs to be initialized before the code is run. User variables can also be bound to a given register, and thereby can be read and written from and to the PFPU. Those registers will then be used exclusively for the constant or user variable.
1741
1742 To differentiate registers used by constants and user variables from registers used to store internal results, the former are given positive numbers by the FPVM compiler while the latter are given negative numbers.
1743
1744 The scheduler then maps all positive FPVM registers to the PFPU register with the same number, so that they can be easily accessed by the user. Negative FPVM registers are dynamically allocated during the scheduling among the remaining PFPU registers.
1745
1746 \section{Results}
1747 The performance of the PFPU depends directly on the performance of the scheduler, that is to say, its ability to take advantage of out-of-order execution opportunities to hide the latencies of the hardware.
1748
1749 We compiled and scheduled a few MilkDrop patches, and counted the resulting number of instructions and the number of cycles after scheduling. The ratio between the two figures is the CPI (Cycles Per Instruction), which represents the average time it takes to execute one instruction. The results are given in table~\ref{tab:gfpusperf}. The ``Default'' patch is a patch that contains no user-defined per-vertex equations, and the instructions correspond to the implicit equations needed to implement the built-in effects (zoom, scaling, ...).
1750
1751 From this table, it is apparent that our approach, albeit simple, is very efficient at extracting instruction-level parallelism. Indeed, the CPI stays between 1.38 and 1.41 while the latencies of the hardware pipelines executing the instructions are much higher, between 2 and 5 (table~\ref{tab:pfpulatency}).
1752
1753 \begin{table}
1754 \centering
1755 \begin{tabularx}{13cm}{|X|l|l|l|l|l|}
1756 \hline
1757 \textbf{Patch} & \textbf{Instructions} & \textbf{Cycles} & \textbf{CPI} \\
1758 \hline
1759 Default & 192 & 259 & 1.35 \\
1760 \hline
1761 Fvese - The Tunnel (Final Stage Mix) (simplified) & 208 & 286 & 1.38 \\
1762 \hline
1763 Geiss - Warp of Dali 1 & 220 & 292 & 1.33 \\
1764 \hline
1765 Krash - Digital Flame (simplified) & 216 & 293 & 1.36 \\
1766 \hline
1767 Unchained \& Rovastar - Wormhole Pillars (Hall of Shadows mix) & 231 & 326 & 1.41 \\
1768 \hline
1769 \end{tabularx}
1770 \caption{Greedy PFPU scheduler performance with the per-vertex math of different MilkDrop patches (Milkymist 0.5.1).}\label{tab:gfpusperf}
1771 \end{table}
1772
1773 \begin{table}
1774 \centering
1775 \begin{tabularx}{13cm}{|X|l|}
1776 \hline
1777 \textbf{Instruction} & \textbf{Latency} \\
1778 \hline
1779 Floating point addition & 4 \\
1780 \hline
1781 Floating point subtraction & 4 \\
1782 \hline
1783 Floating point multiplication & 5 \\
1784 \hline
1785 Floating point absolute value & 2 \\
1786 \hline
1787 Conversion from float to integer & 2 \\
1788 \hline
1789 Conversion from integer to float & 3 \\
1790 \hline
1791 Sine/cosine table look-up & 4 \\
1792 \hline
1793 Comparisons & 2 \\
1794 \hline
1795 Copy & 2 \\
1796 \hline
1797 Conditional & 2 \\
1798 \hline
1799 Inversion of the sign of operand 1 if operand 2 is negative & 2 \\
1800 \hline
1801 Inverse square root approximation & 2 \\
1802 \hline
1803 \end{tabularx}
1804 \caption{PFPU latencies in cycles (Milkymist 0.5.1).}\label{tab:pfpulatency}
1805 \end{table}
1806
1807 To put this in contrast with our initial goals (section~\ref{sec:pfpupurpose}), let us consider a typical patch that performs, per vertex, 150 base operations (addition, subtraction, multiplication), 4 divisions, 4 square root extractions and 20 sine or cosine computations (which is close to the patch used in our initial estimate). According to the table~\ref{tab:pfpucost}, this would mean 318 PFPU instructions. The maximum CPI that lets us achieve our performance goal is therefore 2.56. Our performance goal is easily met, assuming that other patches expose the same opportunities for out-of-order execution.
1808
1809 \begin{table}
1810 \centering
1811 \begin{tabularx}{13cm}{|X|l|l|l|l|l|}
1812 \hline
1813 \textbf{Operation} & \textbf{Instructions} \\
1814 \hline
1815 Addition, subtraction, multiplication & 1 \\
1816 \hline
1817 Sine and cosine & 3 \\
1818 \hline
1819 Inverse square root & 11 \\
1820 \hline
1821 Square root & 12 \\
1822 \hline
1823 Division & 15 \\
1824 \hline
1825 \end{tabularx}
1826 \caption{Exact cost in instructions of common operations on the PFPU.}\label{tab:pfpucost}
1827 \end{table}
1828
1829 \chapter{Software}
1830 \label{ch:sw}
1831 \section{LatticeMico32}
1832 \label{sec:mico32}
1833 The heart of the software execution capabilities of the SoC is the LatticeMico32 microprocessor core~\cite{mico32}. It is a classic 6-stage in-order pipelined RISC processor (figure~\ref{fig:lm32arch}) with a custom instruction set supported by the GNU (GCC-based) compiler toolchain. It supports separate instruction and data caches with up to two ways. There are an optional barrel shifter, pipelined multiplier and multi-cycle divider.
1834
1835 \begin{figure}[htp]
1836 \centering
1837 \includegraphics[height=90mm]{lm32arch.eps}
1838 \caption{LatticeMico32 architecture (Lattice Semiconductor).}
1839 \label{fig:lm32arch}
1840 \end{figure}
1841
1842 The Milkymist system-on-chip uses LatticeMico32 with 2-way caches of 16KB each, and all the optional features enabled.
1843
1844 At the time this thesis is written, LatticeMico32 is the only hardware component that we have not developed specifically for the Milkymist project.
1845
1846 \section{Capabilities}
1847 The ``nommu'' version of Linux has been ported to the Milkymist SoC (figure~\ref{fig:linux}). Since this is a community effort with a significant contribution by Takeshi Matsuya from Keio University, the details are not covered in this Master's thesis. Still, this demonstrates the ability of the platform to run complex software.
1848
1849 \begin{figure}[htp]
1850 \centering
1851 \includegraphics[height=100mm]{linux.eps}
1852 \caption{Linux booting on the Milkymist SoC.}
1853 \label{fig:linux}
1854 \end{figure}
1855
1856 \section{Benchmarking}
1857 The performance of the Milkymist SoC was compared to Microblaze~\cite{microblaze}, the proprietary Xilinx softcore SoC platform.
1858
1859 The benchmark used was the ``consumer'' MiBench~\cite{mibench} suite. By contrast to traditional benchmarks such as SPEC, MiBench is tailored to typical workloads of embedded systems. Only two benchmarks are missing from the ``consumer'' set: \verb!tiff2rgba! (it tried to use too much contiguous memory for the nommu Milkymist/Linux allocator to handle) and \verb!lame! (it crashed on Microblaze).
1860
1861 \begin{figure}[htp]
1862 \centering
1863 \includegraphics[height=100mm]{ml401.eps}
1864 \caption{Xilinx ML401 development board.}
1865 \label{fig:ml401}
1866 \end{figure}
1867
1868 All tests were run on a Xilinx ML401 (XC4VLX25 FPGA, see figure~\ref{fig:ml401}) development board, with a system frequency of 100MHz.
1869
1870 For Milkymist, the configuration used was the default one of the port to the ML401 board:
1871 \begin{itemize}
1872 \item Processor with hardware multiplier, divider and barrel shifter
1873 \item 16KB L1 instruction and data (write-through) cache (2-way set-associative)
1874 \item No memory management unit (LatticeMico32 does not have one)
1875 \item 16KB FML bridge write-back L2 cache (direct mapped)
1876 \item HPDMC DDR SDRAM controller, 32-bit SDRAM bus width
1877 \item 100MHz DDR SDRAM clock
1878 \item Video output running at standard VGA resolution, consuming approximately 300MBps of memory bandwidth
1879 \item Software: GCC 4.2.1 and Linux 2.6.23.
1880 \end{itemize}
1881
1882 For Microblaze, the configuration is as follows:
1883 \begin{itemize}
1884 \item Processor with hardware multiplier, divider and barrel shifter
1885 \item 16KB L1 instruction and data (write-through) cache (direct mapped, multi-way caches are not supported)
1886 \item Full memory management unit
1887 \item No L2 cache (not supported)
1888 \item MPMC DDR SDRAM controller, 32-bit SDRAM bus width
1889 \item 100MHz DDR SDRAM clock
1890 \item No video output
1891 \item Software: GCC 4.1.2 and Linux 2.6.32.4.
1892 \end{itemize}
1893
1894 The comparison seems clearly in favor of Milkymist, with a rough 15\%-35\% (depending on the benchmark) reduction in execution time. Details are shown in figure~\ref{fig:mmvsmb} and in tables \ref{tab:milkymistspeed} and \ref{tab:microblazespeed}. Deviation is computed as:
1895 \begin{equation}
1896 \frac{|t_{1}-t_{2}|}{\textrm{min}(t_{1}, t_{2})}
1897 \end{equation}
1898 It is meant to check that the results are deterministic and reproducible.
1899
1900 \begin{figure}[htp]
1901 \centering
1902 \includegraphics[height=75mm]{mm_vs_mb.eps}
1903 \caption{Comparative MiBench results of Milkymist and Microblaze.}
1904 \label{fig:mmvsmb}
1905 \end{figure}
1906
1907 \begin{table}
1908 \centering
1909 \begin{tabular}{|l|l|l|l|l|}
1910 \hline
1911 \textbf{Benchmark} & \textbf{Run 1} & \textbf{Run 2} & \textbf{Average} & \textbf{Deviation}  \\
1912 \hline
1913 jpeg & 2.57 s & 2.54 s & 2.56 s & 1.18 \% \\
1914 \hline
1915 mad & 5.84 s & 5.87 s & 5.86 s & 0.51 \% \\
1916 \hline
1917 tiff2bw & 9.51 s & 9.69 s & 9.6 s & 1.89 \% \\
1918 \hline
1919 tiffdither & 19.28 s & 19.3 s & 19.29 s & 0.10 \% \\
1920 \hline
1921 tiffmedian & 26.48 s & 26.26 s & 26.37 s & 0.84 \% \\
1922 \hline
1923 typeset & 21.44 s & 21.79 s & 21.62 s & 1.63 \% \\
1924 \hline
1925 \end{tabular}
1926 \caption{User execution times on Milkymist 0.2.}\label{tab:milkymistspeed}
1927 \end{table}
1928
1929 \begin{table}
1930 \centering
1931 \begin{tabular}{|l|l|l|l|l|}
1932 \hline
1933 \textbf{Benchmark} & \textbf{Run 1} & \textbf{Run 2} & \textbf{Average} & \textbf{Deviation}  \\
1934 \hline
1935 jpeg & 3.42 s & 3.58 s & 3.5 s & 4.68 \% \\
1936 \hline
1937 mad & 6.72 s & 7.11 s & 6.92 s & 5.80 \% \\
1938 \hline
1939 tiff2bw & 15.19 s & 14.12 s & 14.66 s & 7.58 \% \\
1940 \hline
1941 tiffdither & 24.72 s & 24.68 s & 24.7 s & 0.16 \% \\
1942 \hline
1943 tiffmedian & 35.02 s & 33.05 s & 34.04 s & 5.96 \% \\
1944 \hline
1945 typeset & 28.91 s & 28.83 s & 28.87 s & 0.28 \% \\
1946 \hline
1947 \end{tabular}
1948 \caption{User execution times on Microblaze 10.1.}\label{tab:microblazespeed}
1949 \end{table}
1950
1951 The root causes of this performance improvement were not investigated; but since LatticeMico32 and Microblaze share a very close architecture, it is suspected that these differences are vastly explained by the combination of the low-latency HPDMC memory controller and the improved caches.
1952
1953 The main point of this comparison is to confirm the viability of Milkymist as a powerful SoC platform, that can withstand the competition with proprietary solutions.
1954
1955 \section{Design of a MilkDrop-like rendering program}
1956 \subsection{Description}
1957 With all those elements at hand, the last task is to design a complete renderer program compatible with MilkDrop. The block diagram of our renderer is given by the figure~\ref{fig:swarch}.
1958
1959 \begin{figure}[htp]
1960 \centering
1961 \includegraphics[width=\textwidth]{swarch.eps}
1962 \caption{Rendering software architecture.}
1963 \label{fig:swarch}
1964 \end{figure}
1965
1966 Before the rendering proper can take place, the code of the patch needs to be parsed and microcode for the PFPU generated (section~\ref{sec:pfpucomp}). This process, implemented entirely in software, is slow (several hundreds of milliseconds) but it is not performance-critical, as it only needs to be done once before the rendering. Furthermore, its results could be cached to allow a smooth transition between pre-defined patches.
1967
1968 The first step of the rendering process is to digitize the audio signal. This is achieved using the system-on-chip's AC97 controller and its device driver. They are programmed to pack the audio samples into buffers, each of them holding exactly the number of samples that corresponds to the desired video frame rate of 30 frames per second. The buffers are written to the memory using DMA through the L2 cache.
1969
1970 The next operation is to analyze each audio buffer to extract its energy content in three frequency bands, in order to generate the \verb!bass!, \verb!mid! and \verb!treb! parameters that can be used in MilkDrop patches to connect the visual effects to sound. This is done using three decimating finite impulse response (FIR) filters, each followed by an accumulator that adds the energies of each sample at its filter's output. This is several times faster than the original MilkDrop implementation, which consisted in performing a Fourier transform followed by a spectral summation of the energies in the three bands, and allows a software implementation. Indeed, this process has been observed to take approximately $8\unit{ms}$ when run on the system-on-chip, which is more than 3 times less than the video frame period. The filters operate directly on the audio data sent into the memory by the AC97 controller, avoiding any time-wasting memory copy.
1971
1972 The next step is to evaluate the per-frame equations. Even though hardware acceleration is not really needed there, this step is still performed on the PFPU in order to re-use the existing compilation and evaluation infrastructure.
1973
1974 Once per-frame parameters are known, the renderer proceeds to evaluating per-vertex equations on the PFPU. This generates the full mesh of vertex coordinates to be used later by the texture mapping unit for distorting the frame.
1975
1976 All the processes we have seen so far are part of the \textit{analysis loop}. Its output is a stream of packets, each packet describing the operations to be done for one frame. One packet contains the audio samples, the results of the audio analysis, the outputs of the per-vertex equations (as well as the fixed patch parameters) and the distortion mesh data. The packet is sent to the \textit{rendering loop}.
1977
1978 Upon reception of the packet, the rendering loop takes its current frame, and runs the TMU (chapter~\ref{ch:tmu}) to distort it.
1979
1980 Then, it superimposes waves, borders and motion vectors on the result. This is implemented in software, as the processor is fast enough for these tasks.
1981
1982 Finally, the TMU is run twice to scale the internal frame buffer to the screen size and to apply the video echo.
1983
1984 The output is now ready to be displayed. This is done by simply instructing the VGA controller to switch to the newly generated frame buffer. The VGA controller then performs the requested buffer switch during the next vertical blanking interval, in order to produce a transition without any tearing artifact. A triple-buffering technique is used so that the software never has to wait for the VGA controller to release a buffer,\footnote{Assuming that the frame rate is less than the screen refresh frequency, which is always the case in practice as the frame rate is limited to 30 fps and all display devices refresh at much more than 30 Hz.} at the expense of an increased memory consumption.
1985
1986 \subsection{Cache coherency}
1987 The system-on-chip provides limited support for cache coherency (section~\ref{sec:coherency}). Therefore, several operations to ensure coherency must be done by the software throughout the rendering process.
1988
1989 \subsubsection{Cache coherency within the analysis loop}
1990 The only precaution that should be taken is to invalidate the L1 cache after each received buffer from the AC97 audio controller.
1991
1992 There is no need to invalidate the any cache after evaluation of the per-frame equations, as the outputs are read directly from the PFPU register file which is mapped in the non-cacheable CSR address space.
1993
1994 The output the per-vertex equations is sent directly to the rendering loop.
1995
1996 \subsubsection{Cache coherency between the analysis and rendering loops}
1997 Among the data sent from the analysis loop, there is one element which is not coherent with respect to the L1 cache: the vertex data generated from the per-vertex equations. However, this data is not read by the CPU but only by the TMU. The latter fetches it from the L2 cache, which is also where the PFPU writes data. Therefore, no operation is needed to ensure cache coherency.
1998
1999 \subsubsection{Cache coherency within the rendering loop}
2000 Most operations are done by the texture mapping unit, which deals directly with the SDRAM. There are two cases where cache coherency issues can arise:
2001 \begin{enumerate}
2002 \item Between the CPU and the TMU during the wave (and other elements) drawing process.
2003 \item Between the CPU and the VGA controller. Indeed, the VGA controller makes coherent transactions with respect to the L2 cache. If the cache holds an outdated copy of the data, it will be used instead of the more recent version in SDRAM.
2004 \end{enumerate}
2005
2006 To solve these issues with a minimal number of cache invalidations, we make sure that the L1 and L2 cache never hold any data from any frame buffer except during the wave drawing process. This is ensured by:
2007 \begin{enumerate}
2008 \item Aligning all frame buffers to a multiple of both the line lengths of the L1 and L2 caches (i.e. of the least common multiple of the line lengths). In our case, this does not add any additional constraint as those buffers already had tighter alignment requirements stemming from the VGA controller and the avoidance of inter-channel cache conflicts within the texture mapping unit.
2009 \item Invalidating the L1 and L2 cache just after the wave drawing process.
2010 \end{enumerate}
2011
2012 \subsection{Event-driven operation}
2013 Our implementation is \textit{event-driven}. Instead of being fully sequential, the software waits for and acts upon events (for example, the texture mapping unit finishing processing, or a new audio buffer being ready). After an event is received, the CPU can either process the data itself (for example, run the FIR filters after a new audio buffer is ready) or run another hardware unit (for example, run the TMU after the PFPU has evaluated the per-vertex equations). This approach improves performance by letting the three main processing units of the system (the CPU, the PFPU and the TMU) operate in parallel.
2014
2015 \subsection{Results}
2016 Our system is able to render successfully many original MilkDrop presets at 30 frames per seconds in 640x480 resolution. However, it is often operating near its limit, and sometimes above it, as some presets exhibit a lower frame rate. This is often due to the fact that drawing the waves and the borders take a long time on the CPU, especially when many semi-transparent pixels need to be drawn. This precludes the possibility of supporting presets that employ complex custom waves and shapes (that would be drawn by the CPU), unless further acceleration techniques are devloped.
2017
2018 \chapter{Conclusion and future works}
2019 \label{ch:conclusion}
2020 Through this thesis project, we have covered many different aspects of computer architecture, which were necessary to achieve our goal of designing a high-performance system-on-chip for video synthesis.
2021
2022 We first exposed the difficulties involved with the amount of memory required for the video synthesis application, and the latency and bandwidth challenges stemming from the DRAM technology. Our solution consisted of a combination of a page mode control algorithm, using of burst transfers with critical-word-first support, and pipelining. It keeps the hardware small and simple, and our results have shown that it allows using the memory bandwidth at roughly half the peak capacity of the chips, which was enough for our application taking into account an oversizing of the memory system.
2023
2024 Then, we explained how we split the system interconnect on three different busses, solving high fanout and large multiplexer problems, enabling devices on different bus segments to communicate in parallel, and having specific bus standards on each segment, depending on the feature and bandwidth needs of the devices using it.
2025
2026 We went on with the problems stemming from the compute-intensive parts of the video rendering process: texture mapping and fast evaluation of the equations that define the texture coordinates. We solved those by developing custom hardware accelerators, the texture mapping unit (TMU) and the programmable floating point unit (PFPU). The PFPU easily exceeded its design goals, but our TMU was challenged by its important consumption of memory bandwidth and the associated memory latencies issues. It was nonetheless able to meet our expectation of enabling the rendering of the video effects in VGA (640x480) resolution.
2027
2028 Finally, we chose and integrated a good CPU core to control the system and perform less compute-intensive and software-friendly tasks. Our choice was the LatticeMico32 core, which, when integrated into our system, exceeded the performance of the competing proprietary Microblaze solution. We wrote video rendering software for it, leveraging the possibilities of our SoC architecture.
2029
2030 Overall, our goal has been met as we have been successful at rendering many MilkDrop presets in VGA resolution on our system at a good frame rate. However, several tracks for computer architecture related improvements can be thought of:
2031 \begin{enumerate}
2032 \item In order to be able to use more memory bandwidth from the SDRAM chips, an out-of-order memory controller could be designed.
2033 \item The texture mapping unit could use a prefetching technique to be less affected by the memory latency. Such a technique could also enable several outstanding memory requests from the texture mapping unit at the same time, allowing the memory controller to reorder them in order to leverage more bandwidth from the SDRAM chips.
2034 \item During the development of the texture mapping unit (which was done in plain Verilog HDL), we felt that it was not very productive to repeatedly design manually the pipeline interlocking logic for each stage. This made us think of an ambitious research project that could consist in designing a programming language that would describe similar pipelines from a higher level of abstraction, which would bring many advantages. First, productivity would be improved as the designer would not have to design and code manually (with a risk of errors) many elements. Second, the language could be simulated to validate the high level functionality of the design. Third, this simulation  could also be used to explore the design space of functionally-equivalent implementations with different area, power and speed performances (for example, by observing the impact on speed that the cache size of a memory access point has in order to strike a good compromise between the two). A computer program could even be used to perform part or all of this exploration in order to meet pre-defined power, area and speed goals, and back-annotate all the design choices it made into the design.
2035
2036 With such a powerful tool, we could, for example, quite easily upgrade the texture mapping unit's graphics pipeline so it could support the full OpenGL ES specification. It could also certainly be used in many other fields unrelated to computer graphics.
2037 \end{enumerate}
2038
2039 The Milkymist project is not entirely about computer architecture and system-on-chip design. We are also working, in collaboration with Sharism at Work Ltd. and other contributors, on building complete ``open source hardware'' products around the SoC described herein. Our first device will be the Milkymist One interactive VJ station. Technical aspects of this wider project also include printed circuit board layout (figure~\ref{fig:mm1}) and software engineering. All of the work is covered by open source licenses.
2040
2041 We hope that this open hardware platform will be successful --- used not only for its intended live video synthesis purpose, but also as a learning tool, as a development platform and as a base or even a design library for other open source projects.
2042
2043 \begin{figure}[htp]
2044 \centering
2045 \includegraphics[width=\textwidth]{mm1.eps}
2046 \caption{Printed circuit board floorplan of the Milkymist One.}
2047 \label{fig:mm1}
2048 \end{figure}
2049
2050 \bibliography{thesis}{}
2051 \bibliographystyle{plain}
2052
2053 \end{document}