draft
[mw/milkymist.git] / doc / thesis.tex
1 % http://www.idt.mdh.se/phd/thesis/kthesis-1.0/
2 \documentclass[a4paper,11pt]{kthesis}
3 \usepackage[T1]{fontenc}
4 \usepackage[normalem]{ulem}
5 \usepackage[english]{babel}
6 \usepackage{boxedminipage}
7 \usepackage{graphicx}
8 \usepackage{moreverb}
9 \usepackage{float}
10 \usepackage{cite}
11 \usepackage{tabularx}
12 \usepackage{units}
13 \usepackage{amsmath}
14 \usepackage{wasysym}
15 \usepackage[first]{draftcopy}
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{ICT-EX-2010:90}
26 \isbn{x-xxxx-xxx-x}
27 \begin{document}
28 \begin{abstract}
29 Commercial system-on-chips with advanced graphics acceleration capabilities are becoming ubiquitous today. However, in contradiction with the open source idea, little is known about the details of their architecture and implementation, as they are usually covered by trade secrets.
30
31 Fostered by the falling costs of high-density FPGAs, our thesis project encompasses researching, developing and implementing the key points of the architecture of an open source and comprehensive system-on-chip with competitive yet reasonable graphics capabilities. The chosen target application is the synthesis of visual effects similar to those produced by the popular MilkDrop visualization plug-in for Winamp.
32
33 Our system-on-chip design consists principally of a custom bus infrastructure, a custom DDR SDRAM memory controller, a microprocessor core, and custom graphics accelerators for texture mapping and floating point processing.
34
35 Our base microprocessor system is capable of running Linux (without MMU) and outperforms a Microblaze-based solution tested in similar conditions by a 15 to 35\% increase in speed of execution. For our video synthesis application, our texture mapping accelerator achieves an average fill rate of 44 megapixels per second and our floating point processing unit provides in excess of 70 million floating point operations per second. Everything, including I/O peripherals (AC97 audio, Ethernet, RS232 UART, GPIO), is implemented on a Virtex-4 XC4VLX25 FPGA, where it utilizes about 80\% of the resources.
36
37 Finally, we have successfully developed an embedded video synthesis program that leverages the possibilities of our hardware architecture to permit the live rendering of many MilkDrop effects in 640x480 resolution at 30 frames per second.
38 \end{abstract}
39
40 \begin{acknowledgments}
41 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 for his help and advice with it.
42
43 I would also like to thank Lattice Semiconductor for opening the source code of their LatticeMico32 processor core.
44
45 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 on board 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.
46
47 Thanks to the Eid\^olon music band (Rheims, France), for whom I wrote my first PC-based video synthesis program in 2005, which has been a source of inspiration for this project.
48
49 Finally, 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.
50
51 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.
52 \end{acknowledgments}
53
54 \tableofcontents
55 \listoffigures
56 \listoftables
57
58 \mainmatter
59
60 \chapter{Introduction}
61 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.
62
63 \begin{figure}[htp]
64 \centering
65 \includegraphics[height=95mm]{ikosboards.eps}
66 \caption{FPGA boards of the Ikos Pegasus ASIC emulator (ca. 1999).}
67 \label{fig:ikos}
68 \end{figure}
69
70 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.
71
72 \begin{figure}
73 \centering
74 \includegraphics[height=55mm]{newlogo.eps}
75 \caption{Project logo.} \label{fig:projectlogo}
76 \end{figure}
77
78 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.
79
80 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:
81 \begin{itemize}
82 \item A device of very small size and weight is possible, which is convenient in mobile or temporary setups.
83 \item Boot and set-up time (launching the software) can be greatly reduced (to a few seconds).
84 \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.
85 \end{itemize}
86
87 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.
88
89 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.
90
91 \chapter{Background}
92 \section{Video synthesis}
93 \subsection{Overview}
94 MilkDrop~\cite{milkdrop} (figure~\ref{fig:milkdrop}) is a popular open source video synthesis framework that was originally made to develop visualization plug-ins 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}.
95
96 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}).
97
98 \begin{figure}[htp]
99 \centering
100 \includegraphics[height=65mm]{milkdrop2.eps}
101 \caption{Sample video frame from the MilkDrop visual synthesizer.}
102 \label{fig:milkdrop}
103 \end{figure}
104
105 \begin{figure}[htp]
106 \centering
107 \includegraphics[height=60mm]{visikord.eps}
108 \caption{Sample video frame from Visikord, a program mixing live video into MilkDrop.}
109 \label{fig:visikord}
110 \end{figure}
111
112 \begin{figure}[htp]
113 \centering
114 \includegraphics[height=85mm]{flickernoise.eps}
115 \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.}
116 \label{fig:flickernoise}
117 \end{figure}
118
119 \subsection{Principle}
120 \label{subsec:mdprinciple}
121 \subsubsection{General mode of operation}
122 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}).
123
124 \begin{figure}[htp]
125 \centering
126 \includegraphics[height=130mm]{renderflow.eps}
127 \caption{Basic MilkDrop rendering flow.}
128 \label{fig:renderflow}
129 \end{figure}
130
131 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.
132 \begin{itemize}
133 \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}.
134 \item The frame is darkened (the colors are shifted to black).
135 \item A waveform of the currently played music is drawn. The wave can be drawn linearly (like an oscilloscope), in a circle, etc.
136 \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).
137 \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.
138 \item The process repeats from the beginning.
139 \end{itemize}
140
141 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.
142
143 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:
144 \begin{itemize}
145 \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).
146 \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.
147 \end{itemize}
148 It must be noted that this two-step process increases the computation time and the consumption of memory bandwidth.
149
150 All the steps of the rendering are heavily parameterizable 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.
151
152 \begin{figure}
153 \centering
154 \begin{boxedminipage}{13cm}
155 \begin{verbatim}
156 fDecay=0.980000
157 nWaveMode=2
158 bTexWrap=1
159 bMotionVectorsOn=0
160 zoom=1.046000
161 rot=0.020000
162 cx=0.500000
163 cy=0.500000
164 warp=0.969000
165 sx=1.000000
166 sy=1.000000
167 wave_r=0.600000
168 wave_g=0.600000
169 wave_b=0.600000
170 wave_x=0.500000
171 wave_y=0.470000
172 per_frame_1=wave_r = wave_r + 0.400*( 0.60*sin(0.933*time)
173   + 0.40*sin(1.045*time) );
174 per_frame_2=wave_g = wave_g + 0.400*( 0.60*sin(0.900*time)
175   + 0.40*sin(0.956*time) );
176 per_frame_3=wave_b = wave_b + 0.400*( 0.60*sin(0.910*time)
177   + 0.40*sin(0.920*time) );
178 per_frame_4=zoom = zoom + 0.010*( 0.60*sin(0.339*time)
179   + 0.40*sin(0.276*time) );
180 per_frame_5=rot = rot + 0.050*( 0.60*sin(0.381*time)
181   + 0.40*sin(0.579*time) );
182 per_frame_6=cx = cx + 0.030*( 0.60*sin(0.374*time)
183   + 0.40*sin(0.294*time) );
184 per_frame_7=cy = cy + 0.030*( 0.60*sin(0.393*time)
185   + 0.40*sin(0.223*time) );
186 per_vertex_1=sx=sx-0.04*sin((y*2-1)*6+(x*2-1)*7+time*1.59);
187 per_vertex_2=sy=sy-0.04*sin((x*2-1)*8-(y*2-1)*5+time*1.43);
188 \end{verbatim}
189 \end{boxedminipage}
190 \caption{Excerpt from the MilkDrop preset ``Geiss -- Warp of Dali 1'' (with some simplifications).}
191 \label{fig:samplepatch}
192 \end{figure}
193
194 \subsubsection{Initial conditions}
195 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:
196 \begin{itemize}
197 \item \verb!bMotionVectorsOn=0! turns off the drawing of the motion vectors.
198 \item \verb!nWaveMode=2! selects one of the many ways of drawing the audio waveform.
199 \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).
200 \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).
201 \end{itemize}
202
203 \subsubsection{Per-frame equations}
204 Using initial conditions only limits the interaction and evolution possibilities of the patch.
205
206 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.
207
208 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!).
209
210 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.
211
212 \subsubsection{Per-vertex equations}
213 Per-vertex equations are used to fine-tune the distortion applied to the picture.
214
215 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).
216
217 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.
218
219 As discussed in chapter~\ref{ch:tmu}, the floating point computations for each vertex are intensive and required the use of a dedicated co-processor.
220
221 \section{Open source SoC platforms}
222 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.
223
224 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:
225 \begin{itemize}
226 \item they have been shown to work on at least one FPGA board
227 \item they are released under an open source license
228 \item they comprise a synthesizable RISC CPU
229 \item the CPU is supported by a C and C++ compiler
230 \item they include a RS232 compatible UART (for a debug console)
231 \item they support interfacing to off-chip SDRAM memory
232 \end{itemize}
233
234 \subsubsection{OpenSPARC}
235 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.
236
237 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.
238
239 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.
240
241 \subsubsection{GRLIB}
242 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 Mb/s Ethernet MAC, 16/32/64-bit DDR SDRAM/DDR2 SDRAM controllers and more.
243
244 However, its drawbacks are:
245 \begin{itemize}
246 \item Code complexity. GRLIB is written in VHDL and makes intensive use of custom types, packages, generate statements, etc.
247 \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.
248 \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.
249 \item Relatively low clock frequency. With the same parameters as above, the maximum clock frequency is 84MHz.
250 \end{itemize}
251
252 Because of these reasons, GRLIB was not retained.
253
254 \subsubsection{ORPSoC (OpenRISC)}
255 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.
256
257 ORPSoC notably features the OpenRISC OR1200 processor core, the Wishbone~\cite{wishbone} bus, comprehensive debugging facilities, a 16550-compatible RS232 UART, a 10/100 Mb/s Ethernet MAC and a SDRAM controller.
258
259 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.
260
261 OpenRISC and ORPSoC therefore do not seem to be a good platform for the performance-demanding and resource-constrained video synthesis application.
262
263 \subsubsection{LatticeMico32 System}
264 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.
265
266 Like its competing products, LatticeMico32 System features a broad library of light, fast and FPGA-optimized SoC cores.
267
268 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.
269
270 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.
271
272 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.
273
274 This microprocessor core has been retained for use in Milkymist, as described in chapter~\ref{ch:sw}.
275
276 \subsubsection{Microblaze and Nios II}
277 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.
278
279 \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 targeting the Virtex-4 family. Thus, Microblaze is close to LatticeMico32 regarding area and frequency.
280
281 \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.
282
283 Some differences can be noted between the LatticeMico32 configuration and the Nios II/f configuration used in the Altera report:
284 \begin{itemize}
285 \item Caches are direct-mapped and 512 bytes (each).
286 \item There is no multiplier.
287 \item Nios II/f uses a dynamic branch predictor, while LatticeMico32 uses a static branch predictor.
288 \item The report does not say if the optional hardware divider, multiplier and shifter (that were enabled in LatticeMico32) were selected.
289 \end{itemize}
290
291 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:
292 \begin{itemize}
293 \item Routing resources and logic delays for the two FPGA families are different.
294 \item It is possible that Altera hand-tuned the Nios II processor to their FPGA technology.
295 \end{itemize}
296
297 \section{DRAM technology}
298 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.
299
300 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.
301
302 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.
303
304 A decoder translates the row address presented to the DRAM device and activates one of the word lines, according to the address.
305
306 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}.
307
308 \begin{figure}
309 \centering
310 \includegraphics[height=100mm]{drambank.eps}
311 \caption{Block diagram of a DRAM memory bank.}
312 \label{fig:drambank}
313 \end{figure}
314
315 Accesses to a SDRAM bank are made as follows:
316 \begin{enumerate}
317 \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}$.
318 \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.
319 \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.
320 \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.
321 \end{enumerate}
322
323 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.
324
325 \subsection{Multiple banks}
326 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.
327
328 Having multiple banks brings two advantages:
329 \begin{itemize}
330 \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.
331 \item Having several rows open (one per bank), which can reduce the number of required row switches and thus improve performance.
332 \end{itemize}
333
334 The controller is responsible for managing the banks, and mapping absolute memory addresses to particular banks. Appropriate bank mapping can improve performance~\cite{pagemode}.
335
336 Standard DDR SDRAM chips come with four internal banks.
337
338 \subsection{Refreshing}
339 Because the DRAM capacitors are not perfect, they gradually lose their charge over time, which results in data corruption.
340
341 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.
342
343 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\%).
344
345 \section{Texture mapping}
346 \label{sec:tm}
347 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.
348
349 \begin{figure}
350 \centering
351 \includegraphics[height=70mm]{tesselsanofi.eps}
352 \caption{Example of distorted picture.}
353 \label{fig:distorted}
354 \end{figure}
355
356 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.
357
358 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.
359
360 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.
361
362 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}).
363
364 \begin{figure}
365 \centering
366 \includegraphics[height=30mm]{bilinear.eps}
367 \caption{Principle of bilinear texture filtering.}
368 \label{fig:bilinear}
369 \end{figure}
370
371 \begin{figure}
372 \centering
373 \includegraphics[height=70mm]{mdbilin.eps}
374 \caption{Rendering with bilinear filtering enabled.}
375 \label{fig:mdbilin}
376 \end{figure}
377
378 \begin{figure}
379 \centering
380 \includegraphics[height=70mm]{mdnearest.eps}
381 \caption{Rendering with bilinear filtering disabled (the nearest texel is used).}
382 \label{fig:mdnearest}
383 \end{figure}
384
385 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.
386
387 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.
388
389 \section{Organization}
390 According to this background, we can derive the following project guidelines:
391
392 \begin{itemize}
393 \item develop a fast, resource-efficient and FPGA-optimized system-on-chip
394 \item develop an efficient memory subsystem
395 \item reuse a light-weight soft-core CPU
396 \item partition carefully the tasks between hardware and software
397 \item develop custom hardware accelerators
398 \end{itemize}
399
400 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.
401
402 More specifically, the following components are not developed yet:
403 \begin{itemize}
404 \item microSD controller (the current prototype use a CF card through Xilinx SystemACE)
405 \item USB controller
406 \item Video input
407 \item IR receiver
408 \item MIDI controller
409 \item DMX512 controller
410 \end{itemize}
411
412 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.
413
414 Graphics processing also requires a significant amount of memory bandwidth, which is discussed in chapter~\ref{ch:memory}.
415
416 Chapter~\ref{ch:intercon} describes the on-chip interconnect used to make the various blocks communicate with one another.
417
418 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.
419
420 \begin{figure}
421 \centering
422 \includegraphics[height=170mm]{soc_architecture.eps}
423 \caption{SoC block diagram.}
424 \label{fig:block}
425 \end{figure}
426
427
428 \chapter{Memory subsystem}
429 \label{ch:memory}
430 \section{Attacking the memory wall}
431 \label{sec:memorywall}
432 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}.
433
434 Memory performance is measured with two metrics:
435 \begin{itemize}
436 \item \textit{bandwidth}, which is the amount of data that the memory system can transfer during a given period of time.
437 \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.
438 \end{itemize}
439
440 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.
441
442 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.
443
444 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.
445
446 Some SDRAM controllers do a lot to optimize bandwidth but have little focus on latency. Bandwidth-optimizing techniques include:
447 \begin{itemize}
448 \item reordering memory transactions to maximize the page mode hit rate.
449 \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 data path.
450 \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.
451 \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 sub-multiple 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.
452 \end{itemize}
453
454 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.
455
456 \section{Another approach}
457 The out-of-order execution and hardware multi-threading 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 targeted 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.
458
459 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.
460
461 The memory system features that improve latency (but also bandwidth) are discussed below.
462
463 \section{Memory system features}
464 \subsection{Single SDRAM and system clock domain}
465 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.
466
467 \subsection{Page mode control algorithm}
468 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.
469
470 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.
471
472 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.
473
474 This optimization positively affects both latency and bandwidth.
475
476 \subsection{Burst accesses}
477 \label{subsec:fmlburst}
478 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.
479
480 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.
481
482 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:
483 \begin{itemize}
484 \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.
485 \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.
486 \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}.
487 \end{itemize}
488
489 \subsection{Burst reordering}
490 \label{subsec:fmlborder}
491 This feature enables the use of the critical-word-first scheme in caches, reducing the overall memory latency.
492
493 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.
494
495 For example, assuming a burst length of 4:
496 \begin{itemize}
497 \item a request at address 0 fetches words 0, 1, 2 and 3 (in this order)
498 \item a request at address 2 fetches words 2, 3, 0 and 1 (in this order)
499 \end{itemize}
500
501 \subsection{Pipelining}
502 \label{subsec:fmlpipe}
503 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:
504
505 \begin{tabular}{|c|c|c|c|c|c|c|c|}
506 \hline
507 \textbf{Address} & A1 & A1 & A1 & A2 & A2 & A2 & A2 \\
508 \hline
509 \textbf{Data} & -- & -- & M(A1) & M(A1+1) & M(A1+2) & M(A1+3) & M(A2) \\
510 \hline
511 \end{tabular}\\
512
513 \begin{tabular}{|c|c|c|c|}
514 \hline
515 \textbf{Address (cont.)} & -- & -- & --\\
516 \hline
517 \textbf{Data (cont.)} & M(A2+1) & M(A2+2) & M(A2+3) \\
518 \hline
519 \end{tabular}
520
521 Together with burst access, this helps achieving 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.
522
523 \section{Practical implementation}
524 \label{sec:memimpl}
525 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.
526
527 \begin{table}
528 \centering
529 \begin{tabularx}{13cm}{|X|l|}
530 \hline
531 \textbf{Task} & \textbf{Required bandwidth} \\
532 \hline
533 VGA frame buffer, 1024x768, 75Hz, 16bpp & 950Mb/s \\
534 \hline
535 Distortion: texture mapping, 512x512 to 512x512, 30fps, 16bpp & 250Mb/s \\
536 \hline
537 Live video: texture mapping, 720x576 to 512x512 with transparency, 30fps, 16bpp & 300Mb/s \\
538 \hline
539 Scaling: texture mapping, 512x512 to 1024x768, 30fps, 16bpp & 500Mb/s \\
540 \hline
541 Video echo: texture mapping, 512x512 to 1024x768 with transparency, 30fps, 16bpp & 900Mb/s \\
542 \hline
543 NTSC input, 720x576, 30fps, 16bpp & 200Mb/s \\
544 \hline
545 Software and misc. & 200Mb/s \\
546 \hline
547 \textbf{Total} & \textbf{3.3Gb/s} \\
548 \hline
549 \end{tabularx}
550 \caption{Estimate of the memory bandwidth consumption.}\label{tab:membw}
551 \end{table}
552
553 The memory is run at 100MHz, yielding a peak theoretical bandwidth of 6.4Gb/s, 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.
554
555 \begin{figure}[H]
556 \centering
557 \includegraphics[height=85mm]{hpdmc_block.eps}
558 \caption{Block diagram of the HPDMC architecture.}\label{fig:hpdmc_block}
559 \end{figure}
560
561 The architecture of the memory controller, called HPDMC (for ``High Performance Dynamic Memory Controller''), is outlined in figure~\ref{fig:hpdmc_block}.
562
563 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.
564
565 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.
566
567 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.
568
569 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.
570
571 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.
572
573 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 on board the international space station in 2011. Gregory Taylor, Electronics Engineer at the NASA Jet Propulsion Laboratory, wrote:
574
575 \textit{While searching for a suitable SDRAM controller for the Jet Propulsion Laboratory's Software-Defined Radio on board 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.}
576
577 \textit{The Communication Navigation and Networking Reconfigurable Testbed (CoNNeCT) experiment to be installed on board 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.}
578
579 \section{Performance measurement}
580 \label{sec:memperf}
581 \subsection{Introduction}
582 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.
583
584 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.
585
586 \subsection{Method}
587 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.
588
589 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:
590 \begin{itemize}
591 \item the \textbf{net bandwidth} carried by the link (based on the amount of data that the link has actually transferred)
592 \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.
593 \item the \textbf{bus occupancy} which is the percentage of time during which the link was busy and therefore unavailable for a new request.
594 \end{itemize}
595
596 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 de-asserted (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.
597
598 \begin{figure}
599 \centering
600 \includegraphics[height=40mm]{fmltransactions.eps}
601 \caption{FML transactions.} \label{fig:fmltransactions}
602 \end{figure}
603
604 In the equations that follow, these symbols are used:
605 \begin{itemize}
606 \item $f$ is the system clock frequency in Hz.
607 \item $T$ is the time during which the counters have been enabled.
608 \item $w$ is the width of a FML word in bits.
609 \item $n$ is the FML burst length.
610 \item $S$ is the number of cycles during which the strobe signal was active.
611 \item $A$ is the number of cycles during which the acknowledgement signal was active.
612 \end{itemize}
613
614 \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:
615 \begin{equation}
616 \beta = \frac{w \cdot n \cdot A}{T}
617 \end{equation}
618
619 \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:
620 \begin{equation}
621 \Delta = \frac{S-A}{A}
622 \end{equation}
623
624 \begin{figure}
625 \centering
626 \includegraphics[height=45mm]{fmlmax.eps}
627 \caption{Maximum utilization of a FML bus.} \label{fig:fmlmax}
628 \end{figure}
629
630 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 transaction is transferred.
631
632 Therefore, only a fraction $\alpha$ of the peak bandwidth $f \cdot w$ can be used at most, and we have:
633 \begin{equation}
634 \alpha = \textrm{max}(1, \frac{n}{\Delta+1})
635 \end{equation}
636
637 The maximum bandwidth is:
638 \begin{equation}
639 \beta_{max} = \alpha \cdot f \cdot w
640 \end{equation}
641
642 \paragraph{Bus occupancy.} The bus is busy when the strobe signal is asserted. The bus occupancy is therefore given by:
643 \begin{equation}
644 \epsilon = \frac{S}{T \cdot f}
645 \end{equation}
646
647 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.
648
649 \subsection{Results}
650 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.
651
652 \begin{table}
653 \centering
654 \begin{tabular}{|l|l|l|l|l|l|}
655 \hline
656 \textbf{Patch} & $\beta$ & $\epsilon$ & $\Delta$ & $\alpha$ & $\beta_{max}$ \\
657 \hline
658 Idle & 292 & 7 \% & 5.51 & 61 \% & 3932 \\
659 \hline
660 Geiss - Bright Fiber Matrix 1 & 990 & 28 \% & 6.37 & 54 \% & 3474 \\
661 \hline
662 Geiss - Swirlie 3 & 1080 & 32 \% & 6.71 & 52 \% & 3320 \\
663 \hline
664 Geiss - Spacedust & 1021 & 29 \% & 6.47 & 54 \% & 3427 \\
665 \hline
666 Illusion \& Rovastar - Snowflake Delight & 1399 & 39 \% & 6.28 & 55 \% & 3516 \\
667 \hline
668 Rovastar \& Idiot24-7 - Balk Acid & 1427 & 41 \% & 6.38 & 54 \% & 3469 \\
669 \hline
670 \end{tabular}
671 \caption{Memory performance in different conditions (Milkymist 0.5.1). Bandwidths are in Mb/s.}\label{tab:memperformance}
672 \end{table}
673
674 It is difficult to compare these results to those of other memory controllers as they are usually not published (or not measured at all).
675
676 However, two conclusions can be drawn:
677 \begin{itemize}
678 \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 Gb/s bandwidth requirement that was estimated in section~\ref{sec:memimpl} seems attainable, although challenging.
679 \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.
680 \end{itemize}
681
682 \chapter{SoC interconnect}
683 \label{ch:intercon}
684 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.
685
686 The general SoC block diagram and its interconnect is outlined in figure~\ref{fig:block}.
687
688 \section{General SoC interconnect: the Wishbone bus}
689 Wishbone~\cite{wishbone} is a general purpose royalty-free SoC bus with open specifications, advocated by the maintainers of the OpenCores.org website.
690
691 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.
692
693 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.
694
695 The data width used for the Wishbone bus is 32, yielding a peak bandwidth of 3.2Gb/s when the system is running at 100MHz.
696
697 \section{Configuration and Status Registers: the CSR bus}
698 Milkymist uses memory-mapped I/O through configuration and status registers.
699
700 If these registers were directly accessed by the Wishbone CPU bus, two problems would arise:
701 \begin{itemize}
702 \item Connecting all peripherals on the same Wishbone bus involves large multiplexers and high fanout signals, posing routing and timing problems.
703 \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.
704 \end{itemize}
705
706 To alleviate these problems, the CSR bus has been developed~\cite{csr} and used in the system through a bus bridge.
707
708 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.
709
710 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.
711
712 \section{High-throughput memory access bus: the FML bus}
713 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.
714
715 \subsection{Variable latency}
716 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.
717
718 \subsection{Burst only}
719 SDRAM is best accessed in burst mode (see subsection~\ref{subsec:fmlburst}).
720
721 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. Furthermore, supporting multiple burst lengths makes the scheduling of the transfers more complex to avoid ``overlapping'' transfers that would create conflicts at the data pins.
722
723 Therefore, in order to greatly simplify the memory controller, all transfers on FML are made using a fixed and pre-defined burst length.
724
725 \subsection{Burst reordering}
726 This was discussed in subsection~\ref{subsec:fmlborder}.
727
728 \subsection{Pipelining}
729 The benefits of this feature have already been discussed in subsection~\ref{subsec:fmlpipe}.
730
731 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.
732
733 \subsection{Usage}
734 The data width used for the FML bus is 64, yielding a peak bandwidth of 6.4Gb/s 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}.
735
736 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).
737
738 In the Milkymist SoC, they are comprised of:
739 \begin{itemize}
740 \item the VGA output controller, which needs to continuously scan a frame buffer up to several megabytes in size to generate the video signal.
741 \item the (planned) video input, which writes, every second, dozens of digitized video frames weighting hundreds of kilobytes each.
742 \item the texture mapping unit (chapter~\ref{ch:tmu}), which needs to deal with large textures at high speed.
743 \end{itemize}
744
745 \section{Bridging Wishbone to FML}
746 \label{sec:fmlbrg}
747 For Wishbone masters (like the CPU) to access SDRAM transparently, it is necessary to bridge the FML bus to the Wishbone bus.
748
749 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.
750
751 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.
752
753 \section{Cache coherency}
754 \label{sec:coherency}
755 \subsection{Coherency issues around the CPU (L1) cache}
756 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:
757 \begin{itemize}
758 \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.
759 \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 retrieve them.
760 \end{itemize}
761
762 It is noteworthy that the CSR address space is non-cache-able, therefore no cache-related precaution should be taken when reading or writing CSRs.
763
764 \subsection{Coherency issues around the Wishbone-FML (L2) cache}
765 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:
766 \begin{itemize}
767 \item The CPU may read a cached copy of a data that has been modified by a FML master.
768 \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.
769 \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.
770 \end{itemize}
771
772 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.
773
774 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.
775
776 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.
777
778 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).
779
780 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}).
781
782 \chapter{Texture mapping unit}
783 \label{ch:tmu}
784 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.
785
786 \section{Algorithm}
787 \subsection{Two-dimensional interpolation}
788 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.
789
790 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.
791
792 \begin{figure}[htp]
793 \centering
794 \includegraphics[height=50mm]{tridec.eps}
795 \caption{Typical decomposition into triangular primitives of the MilkDrop rendering surface.}
796 \label{fig:tridec}
797 \end{figure}
798
799 We then split the 2D interpolation problem into 1D interpolation problems as follows:
800 \begin{itemize}
801 \item The X and Y texture coordinates are interpolated independently.
802 \item First, each coordinate is interpolated on the vertical edges of the rectangles (vertical interpolation) for each integer value of the ordinate.
803 \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.
804 \end{itemize}
805 The process is illustrated in figure~\ref{fig:rectinter}.
806
807 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.
808
809 \begin{figure}[htp]
810 \centering
811 \includegraphics[height=70mm]{rectinter.eps}
812 \caption{2D linear interpolation on a rectangle.}
813 \label{fig:rectinter}
814 \end{figure}
815
816 \subsection{One-dimensional interpolation}
817 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.
818
819 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).}).
820
821 \begin{figure}
822 \centering
823 \begin{boxedminipage}{13cm}
824 \begin{math}
825 Dy \leftarrow y_{1} - y_{0} \\
826 Dx \leftarrow x_{1} - x_{0} \\
827 Q \leftarrow Dy / Dx \footnote{/ is the integer division operator} \\
828 R \leftarrow Dy \% Dx \footnote{\% is the integer modulo operator}  \\
829 x \leftarrow x_{0} \\
830 \hspace{0cm} [y] \leftarrow y_{0} \\ % WA: latex doesn't like lines starting with [
831 e \leftarrow 0 \\
832 \textrm{result(x)} \leftarrow [y] \\
833 \textrm{\textbf{while}~} x < x_{1} \\
834 \textrm{~~~~~} x \leftarrow x + 1 \\
835 \textrm{~~~~~} [y] \leftarrow [y] + Q \\
836 \textrm{~~~~~} e \leftarrow e + R \\
837 \textrm{~~~~~\textbf{if}~} 2\cdot e > Dx \\
838 \textrm{~~~~~~~~~~} [y] \leftarrow [y] + 1 \\
839 \textrm{~~~~~~~~~~} e \leftarrow e - Dx \\
840 \textrm{~~~~~\textbf{end}} \\
841 \textrm{~~~~~result(x)} \leftarrow [y] \\
842 \textrm{\textbf{end}}
843 \end{math}
844 \end{boxedminipage}
845 \caption{One-dimensional linear interpolation algorithm.}
846 \label{fig:interalgo}
847 \end{figure}
848
849 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$):
850 \begin{enumerate}
851 \item $|e| \leq \frac{Dx}{2}$ (which implies $|\frac{e}{Dx}| \leq \frac{1}{2}$)
852 \item The perfect (rational) interpolated value $y$ is equal to $y = [y] + \frac{e}{Dx}$.
853 \end{enumerate}
854
855 These conditions can be proven true by recursion:
856 \begin{enumerate}
857 \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$.
858
859 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$.
860
861 After the first instruction:
862 \begin{itemize}
863 \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 hypothesis).
864 \item if $e$ was positive, it was inferior or equal to $\frac{Dx}{2}$ (because of the recursion hypothesis), therefore we have $0 < e < \frac{3 \cdot Dx}{2} $.
865 \end{itemize}
866 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$
867
868 \item We need to prove that every time the result is being written, the following equation is verified:
869 \begin{equation}
870 \hspace{0cm} [y] + \frac{e}{Dx} = y_{0} + \frac{y_{1}-y_{0}}{x_{1}-x_{0}} \cdot (x - x_{0})
871 \end{equation}
872 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$.
873
874 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:
875 \begin{equation}
876 \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}
877 \end{equation}
878 \begin{equation}
879 \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}} \\
880 \end{equation}
881 \begin{equation}
882 \hspace{0cm} [y] + \frac{e}{Dx} = y_{0} + \frac{y_{1}-y_{0}}{x_{1}-x_{0}} \cdot ((x + 1) - x_{0})
883 \end{equation}
884 $\Box$
885 \end{enumerate}
886
887 \subsection{Bilinear filtering}
888 \label{subsec:bilfpformat}
889 As outlined in section~\ref{sec:tm}, bilinear filtering is needed to obtain good rendering results.
890
891 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).
892
893 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.
894
895 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.
896
897 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).
898
899 \begin{figure}[htp]
900 \centering
901 \includegraphics[height=85mm]{filtfromfp.eps}
902 \caption{Bilinear filtering using the fixed point texture coordinates.}
903 \label{fig:filtfromfp}
904 \end{figure}
905
906 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:
907 \begin{equation}\label{eq:bfilter}
908 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}}
909 \end{equation}
910
911 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$.
912
913 \section{Performance considerations}
914 \subsection{Context}
915 \label{subsec:perfcontext}
916 To motivate the implementation choice of the texture mapping, we will study its execution time in the following  situation:
917 \begin{itemize}
918 \item The size of the source (texture) and destination pictures is 512x512.
919 \item The size of the primitive rectangles is 16x16.
920 \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.
921 \item The system clock is 100MHz.
922 \item The $2\cdot e > Dx$ test is always false (which is optimistic).
923 \item We optimistically do not take into account the extra instructions needed to handle interpolations with a negative slope ($y_{0} > y_{1}$).
924 \end{itemize}
925
926 For a software implementation, we use the cost estimates of table~\ref{tab:swcost}.
927
928 \begin{table}
929 \centering
930 \begin{tabular}{|l|l|}
931 \hline
932 \textbf{Operation} & \textbf{Cost} \\
933 \hline
934 Addition or subtraction & 1 cycle \\
935 \hline
936 Multiplication & 2 cycles \\
937 \hline
938 Division or modulo & 32 cycles \\
939 \hline
940 Bit shift & 1 cycle \\
941 \hline
942 Test (<, >, =, etc.) & 1 cycle \\
943 \hline
944 Conditional jump & 3 cycles \\
945 \hline
946 Assignment & free (which is optimistic) \\
947 \hline
948 Reading or writing to the frame buffer & 2 cycles \\
949 \hline
950 \end{tabular}
951 \caption{Estimates of the cost of common software operations.}\label{tab:swcost}
952 \end{table}
953
954 \subsection{Execution time of the interpolation algorithm}
955 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}.
956
957 \begin{table}
958 \centering
959 \begin{tabular}{|l|l|}
960 \hline
961 \textbf{Operation} & \textbf{Cycles} \\
962 \hline
963 2 subtractions & $2$ \\
964 \hline
965 Division & $32$ \\
966 \hline
967 Modulo & $32$ \\
968 \hline
969 Test & $n$ \\
970 \hline
971 Conditional jump & $3 \cdot n$ \\
972 \hline
973 3 additions & $3 \cdot n$ \\
974 \hline
975 Bit shift (multiply by 2) & $n$ \\
976 \hline
977 Test & $n$ \\
978 \hline
979 Conditional jump & $3 \cdot n$ \\
980 \hline
981 \textbf{Total} & $66 + 12 \cdot n$ \\
982 \hline
983 \end{tabular}
984 \caption{Detailed estimate of the execution time of the interpolation algorithm.}\label{tab:intertime}
985 \end{table}
986
987 \subsection{Total execution time}
988 Using the above formula with $n=15$, we can compute an estimate of the execution time of a software implementation (table~\ref{tab:swtmutime}).
989
990 1D interpolations need to be done twice, once for each texture coordinate.
991
992 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.
993
994 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.
995
996 \begin{table}
997 \centering
998 \begin{tabular}{|l|l|l|}
999 \hline
1000 \textbf{Operation} & \textbf{Cycles} & \textbf{Time} \\
1001 \hline
1002 Vertical interpolation & 503808 & 5 ms \\
1003 \hline
1004 Horizontal interpolation & 8060928 & 81 ms \\
1005 \hline
1006 Frame buffer reads & 2097152 & 21 ms \\
1007 \hline
1008 Bilinear filtering & 19660800 & 197 ms \\
1009 \hline
1010 Frame buffer writes & 524288 & 5 ms \\
1011 \hline
1012 \textbf{Total} & 30846976 & 308 ms \\
1013 \hline
1014 \end{tabular}
1015 \caption{Optimistic estimate of the execution time of software texture mapping.}\label{tab:swtmutime}
1016 \end{table}
1017
1018 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.
1019
1020 \section{Pipelined hardware implementation}
1021 \subsection{Strategy}
1022 \label{subsec:tmustrategy}
1023 Given the performance constraints and the slowness of software implementations, we decided to implement the complete texture mapping process in hardware.
1024
1025 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.
1026
1027 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}.}
1028
1029 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 congestion, making it easier to achieve timing closure in FPGAs.
1030
1031 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.
1032
1033 \begin{figure}[htp]
1034 \centering
1035 \includegraphics[height=165mm]{tmublock.eps}
1036 \caption{Block diagram of the texture mapping unit architecture.}
1037 \label{fig:tmublock}
1038 \end{figure}
1039
1040 \subsection{Vertex fetch engine}
1041 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.
1042
1043 The vertex fetch engine is connected to the lower-bandwidth Wishbone bus because this saves resources compared to FML (which has a wider data path) and makes it easier to handle cache coherency issues (section~\ref{sec:coherency}).
1044
1045 \subsection{Interpolators}
1046 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}.
1047
1048 The vertical interpolator contains two vector interpolators, one for each vertical edge of the rectangle.
1049
1050 \begin{figure}[htp]
1051 \centering
1052 \includegraphics[height=70mm]{vectinter.eps}
1053 \caption{Vector interpolator.}
1054 \label{fig:vectinter}
1055 \end{figure}
1056
1057 \begin{figure}[htp]
1058 \centering
1059 \includegraphics[height=85mm]{pipeinter.eps}
1060 \caption{Pipelined scalar interpolator.}
1061 \label{fig:pipeinter}
1062 \end{figure}
1063
1064 \subsubsection{Stages of the scalar interpolator}
1065 \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 arithmetic combinatorial functions, which compute the two differences in one clock cycle.
1066
1067 \paragraph{Stage B: Q and R computation.} The next operation is to perform the Euclidean 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).
1068
1069 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.
1070
1071 \paragraph{Stage C: Interpolation loop.}
1072 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}$.
1073
1074 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.
1075
1076 \subsection{Clamping/wrapping}
1077 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).
1078
1079 There are two, selectable, ways of dealing with them:
1080 \begin{itemize}
1081 \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).
1082 \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.
1083 \end{itemize}
1084
1085 This stage is implemented by simple arithmetic combinatorial functions, which are registered and pipelined on two sub-stages to meet timing requirements.
1086
1087 \subsection{Address generator}
1088 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.
1089
1090 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:
1091 \begin{equation}\label{eq:fbadr}
1092 A = A_{base} + (H \cdot y + x) \cdot 2
1093 \end{equation}
1094
1095 \subsection{Texel cache}
1096 \label{subsec:texelcache}
1097 \subsubsection{Presentation}
1098 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.
1099
1100 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.
1101
1102 Channel are numbered as follows (see figure~\ref{fig:bilinear}):
1103 \begin{itemize}
1104 \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.
1105 \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.
1106 \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.
1107 \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.
1108 \end{itemize}
1109
1110 \subsubsection{Separate vs. shared caches}
1111 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:
1112 \begin{enumerate}
1113 \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.
1114 \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.
1115 \end{enumerate}
1116 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.
1117
1118 A more efficient solution, which has been retained, consists therefore in having a single multi-ported data store.
1119
1120 \subsubsection{Implementation}
1121 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.
1122
1123 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.
1124
1125 \begin{figure}[htp]
1126 \centering
1127 \includegraphics[height=100mm]{tcarch.eps}
1128 \caption{Architecture of the four-channel texel cache.}
1129 \label{fig:tcarch}
1130 \end{figure}
1131
1132 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.
1133
1134 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.
1135
1136 \subsubsection{Inter-channel cache conflicts}
1137 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.
1138
1139 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.}
1140
1141 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.
1142
1143 For simplicity, we use the pixel (2 bytes) as unit. In the equations that follow:
1144 \begin{itemize}
1145 \item $H$ is the horizontal texture resolution in pixels.
1146 \item $V$ is the vertical texture resolution in pixels.
1147 \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.
1148 \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.
1149 \end{itemize}
1150
1151 \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:
1152 \begin{equation}
1153 l_{p} = \left\lfloor \frac{a_{p}}{N_{l}} \right\rfloor \pmod{\frac{N_{c}}{N_{l}}}
1154 \end{equation}
1155 Thus, two pixels at addresses $a_{1}$ and $a_{2}$ conflict in the cache if and only if:
1156 \begin{equation}\label{eq:cacheconflict}
1157 \begin{cases}
1158 |a_{1}-a_{2}| \geq N_{l} \\
1159 \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}}}
1160 \end{cases}
1161 \end{equation}
1162
1163 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.
1164
1165 \paragraph{Conflicts between channels 1 and 2 (or 3 and 4).}
1166 \begin{figure}[htp]
1167 \centering
1168 \includegraphics[height=55mm]{chdisp_common.eps}
1169 \caption{Disposition of the channels within the texture, general case.}\label{fig:chdispcommon}
1170 \end{figure}
1171 \begin{figure}[htp]
1172 \centering
1173 \includegraphics[height=55mm]{chdisp_vwrap.eps}
1174 \caption{Disposition of the channels within the texture, vertical wrapping.}\label{fig:chdispvwrap}
1175 \end{figure}
1176 The addresses $a_{A}$ and $a_{B}$ of these two channels can be separated by either:
1177 \begin{itemize}
1178 \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.
1179 \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:
1180 \begin{equation}\label{eq:noconflictwrap1}
1181 \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}}}
1182 \end{equation}
1183
1184 To make sure that this condition is verified for all possible pixel addresses, it is sufficient to check that:
1185 \begin{equation}
1186 \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}}}
1187 \end{equation}
1188 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:
1189 \begin{equation}
1190 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}}}
1191 \end{equation}
1192 which leads easily to the result, considering that $\left\lfloor \frac{a}{N_{l}} \right\rfloor = 0$.
1193
1194 This can be further simplified:
1195 \begin{equation}
1196 \begin{cases}
1197 \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1198 1 + \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1199 \end{cases}
1200 \end{equation}
1201 \end{itemize}
1202
1203 \paragraph{Conflicts between channels 1 and 3 (or 2 and 4).}
1204 \begin{figure}[htp]
1205 \centering
1206 \includegraphics[height=55mm]{chdisp_hwrap.eps}
1207 \caption{Disposition of the channels within the texture, horizontal wrapping.}\label{fig:chdisphwrap}
1208 \end{figure}
1209 The separation between the channels' addresses can be:
1210 \begin{itemize}
1211 \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:
1212 \begin{equation}
1213 \begin{cases}
1214 \left\lfloor \frac{H}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1215 1 + \left\lfloor \frac{H}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1216 \end{cases}
1217 \end{equation}
1218 \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:
1219 \begin{equation}
1220 \begin{cases}
1221 \left\lfloor \frac{H \cdot (V-1)}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1222 1 + \left\lfloor \frac{H \cdot (V-1)}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1223 \end{cases}
1224 \end{equation}
1225 \end{itemize}
1226
1227 \paragraph{Conflicts between channels 1 and 4.}
1228 \begin{figure}[htp]
1229 \centering
1230 \includegraphics[height=55mm]{chdisp_hvwrap.eps}
1231 \caption{Disposition of the channels within the texture, horizontal and vertical wrapping.}\label{fig:chdisphvwrap}
1232 \end{figure}
1233 The channels' addresses can be separated by:
1234 \begin{itemize}
1235 \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:
1236 \begin{equation}
1237 \begin{cases}
1238 \left\lfloor \frac{H+1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1239 1 + \left\lfloor \frac{H+1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1240 \end{cases}
1241 \end{equation}
1242 \item 1 pixel in case of vertical wrapping (figure~\ref{fig:chdispvwrap}). This cannot cause ICCCs.
1243 \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:
1244 \begin{equation}
1245 \begin{cases}
1246 \left\lfloor \frac{H \cdot (V-1) - 1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1247 1 + \left\lfloor \frac{H \cdot (V-1) - 1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1248 \end{cases}
1249 \end{equation}
1250 \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:
1251 \begin{equation}
1252 \begin{cases}
1253 \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1254 1 + \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1255 \end{cases}
1256 \end{equation}
1257 \end{itemize}
1258
1259 \paragraph{Conflicts between channels 2 and 3.}
1260 Like above, we can check that $H-1 < N_{l}$ or:
1261 \begin{equation}
1262 \begin{cases}
1263 \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}} \\
1264 1 + \left\lfloor \frac{H-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1265 \end{cases}
1266 \end{equation}
1267
1268 Furthermore, if texture wrapping is enabled, the differences between pixel addresses can become (resulting in similar conditions to check for):
1269 \begin{itemize}
1270 \item $2 \cdot H - 1$ (vertical wrapping, figure~\ref{fig:chdispvwrap}).
1271 \item $H \cdot (V - 1) + 1$ (horizontal wrapping, figure~\ref{fig:chdisphwrap}).
1272 \item $H \cdot (V - 2) + 1$ (wrapping in both directions, figure~\ref{fig:chdisphvwrap}).
1273 \end{itemize}
1274
1275 \paragraph{Summary.}
1276 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}}$):
1277 \begin{equation}\label{eq:icccsum}
1278 \boxed{
1279 \begin{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 H < N_{l} & \textrm{ or } \begin{cases}
1285 \left\lfloor \frac{H}{N_{l}} \right\rfloor \not \equiv 0 \\
1286 1 + \left\lfloor \frac{H}{N_{l}} \right\rfloor \not \equiv 0
1287 \end{cases} \\
1288 H+1 < N_{l} & \textrm{ or } \begin{cases}
1289 \left\lfloor \frac{H+1}{N_{l}} \right\rfloor \not \equiv 0 \\
1290 1 + \left\lfloor \frac{H+1}{N_{l}} \right\rfloor \not \equiv 0
1291 \end{cases}
1292 \end{cases}
1293 }
1294 \end{equation}
1295
1296 If texture wrapping is used, additional conditions appear:
1297 \begin{equation}\label{eq:icccsumwrap}
1298 \boxed{
1299 \begin{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-1) < N_{l} & \textrm{ or } \begin{cases}
1305 \left\lfloor \frac{H \cdot (V-1)}{N_{l}} \right\rfloor \not \equiv 0 \\
1306 1 + \left\lfloor \frac{H \cdot (V-1)}{N_{l}} \right\rfloor \not \equiv 0
1307 \end{cases} \\
1308 H \cdot (V-1) + 1 < N_{l} & \textrm{ or } \begin{cases}
1309 \left\lfloor \frac{H \cdot (V-1) + 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1310 1 + \left\lfloor \frac{H \cdot (V-1) + 1}{N_{l}} \right\rfloor \not \equiv 0
1311 \end{cases} \\
1312 H \cdot (V-2) + 1 < N_{l} & \textrm{ or } \begin{cases}
1313 \left\lfloor \frac{H \cdot (V-2) + 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1314 1 + \left\lfloor \frac{H \cdot (V-2) + 1}{N_{l}} \right\rfloor \not \equiv 0
1315 \end{cases} \\
1316 2 \cdot H - 1 < N_{l} & \textrm{ or } \begin{cases}
1317 \left\lfloor \frac{2 \cdot H - 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1318 1 + \left\lfloor \frac{2 \cdot H - 1}{N_{l}} \right\rfloor \not \equiv 0
1319 \end{cases} \\
1320 H \cdot V - 1 < N_{l} & \textrm{ or } \begin{cases}
1321 \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \not \equiv 0 \\
1322 1 + \left\lfloor \frac{H \cdot V - 1}{N_{l}} \right\rfloor \not \equiv 0
1323 \end{cases}
1324 \end{cases}
1325 }
1326 \end{equation}
1327
1328 \subsubsection{Cache size}
1329 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.
1330
1331 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.}
1332
1333 The source and destination images have a resolution of 512x512 pixels, and are tessellated 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.
1334
1335 The sets were chosen for the following reasons:
1336 \begin{itemize}
1337 \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.
1338 \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.
1339 \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.
1340 \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.
1341 \end{itemize}
1342
1343 \begin{table}
1344 \centering
1345 \begin{tabularx}{13cm}{|c|c|X|X|}
1346 \hline
1347 \textbf{Set name} & \textbf{Output picture} & \textbf{X} & \textbf{Y} \\
1348 \hline
1349 copy & Figure~\ref{fig:tmuoutcopy} & $x \cdot 16 \cdot 64$ & $y \cdot 16 \cdot 64$ \\
1350 \hline
1351 zoomin & Figure~\ref{fig:tmuoutzoomin} & $x \cdot 10 \cdot 64$ & $y \cdot 10 \cdot 64$ \\
1352 \hline
1353 zoomout & Figure~\ref{fig:tmuoutzoomout} & $x \cdot 40 \cdot 64$ & $y \cdot 40 \cdot 64$ \\
1354 \hline
1355 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$ \\
1356 \hline
1357 \end{tabularx}
1358 \caption{Texture coordinate sets used for benchmarking the texel cache.}\label{tab:tcsets}
1359 \end{table}
1360
1361 \begin{figure}[htp]
1362 \centering
1363 \includegraphics[height=85mm]{tmuout_copy.eps}
1364 \caption{TMU output picture for the ``copy'' set (original picture).}
1365 \label{fig:tmuoutcopy}
1366 \end{figure}
1367
1368 \begin{figure}[htp]
1369 \centering
1370 \includegraphics[height=85mm]{tmuout_zoomin.eps}
1371 \caption{TMU output picture for the ``zoomin'' set.}
1372 \label{fig:tmuoutzoomin}
1373 \end{figure}
1374
1375 \begin{figure}[htp]
1376 \centering
1377 \includegraphics[height=85mm]{tmuout_zoomout.eps}
1378 \caption{TMU output picture for the ``zoomout'' set.}
1379 \label{fig:tmuoutzoomout}
1380 \end{figure}
1381
1382 \begin{figure}[htp]
1383 \centering
1384 \includegraphics[height=85mm]{tmuout_rotozoom.eps}
1385 \caption{TMU output picture for the ``rotozoom'' set.}
1386 \label{fig:tmuoutrotozoom}
1387 \end{figure}
1388
1389 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.
1390
1391 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.
1392
1393 \begin{figure}
1394 \centering
1395 \begin{boxedminipage}{13cm}
1396 \begin{verbatim}
1397 $ make TB=tb_tmu2.v
1398 cver +loadvpi=./vpi_images.so:vpi_register tb_tmu2.v
1399 (...)
1400 GPLCVER_2.12a of 05/16/07 (Linux-elf).
1401 Copyright (c) 1991-2007 Pragmatic C Software Corp.
1402   All Rights reserved.  Licensed under the GNU General Public
1403   License (GPL).
1404   See the 'COPYING' file for details.  NO WARRANTY provided.
1405 Today is Tue May  4 14:46:22 2010.
1406 PLI Image I/O functions registered
1407 Compiling source file "tb_tmu2.v"
1408 Compiling source file "../rtl/tmu2_adrgen.v"
1409 (...)
1410
1411 Opening input picture...
1412 Configuring TMU...
1413 CSR write: 0000002c=01000000
1414 CSR write: 00000004=00000020
1415 (...)
1416 CSR write: 00000044=00000010
1417 CSR write: 00000048=0000003f
1418 Starting TMU...
1419 CSR write: 00000000=00000001
1420 Received DONE IRQ from TMU!
1421 Gathering texel cache statistics...
1422 CSR read : 00000050=00040000
1423 CSR read : 00000054=0003c000
1424 (...)
1425 CSR read : 00000068=00000000
1426 CSR read : 0000006c=00000000
1427 Channel A:      245760 /      262144 hits (93.750000 %)
1428 Channel B:           0 /           0 hits (nan %)
1429 Channel C:           0 /           0 hits (nan %)
1430 Channel D:           0 /           0 hits (nan %)
1431 GLOBAL   :      245760 /      262144 hits (93.750000 %)
1432 Writing output picture...
1433 All done!
1434 Halted at location **tb_tmu2.v(367) time 4585546 from call
1435 to $finish.
1436   There were 0 error(s), 32 warning(s), and 402 inform(s).
1437 \end{verbatim}
1438 \end{boxedminipage}
1439 \caption{Typical TMU simulation trace (excerpt).}
1440 \label{fig:tmusimtrace}
1441 \end{figure}
1442
1443 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).
1444
1445 \begin{table}
1446 \centering
1447 \begin{tabular}{|c|c|c|c|c|}
1448 \hline
1449 \textbf{Cache size} & \textbf{copy} & \textbf{zoomin} & \textbf{zoomout} & \textbf{rotozoom} \\
1450 \hline
1451 2kB & 93.75 \% & 98.08 \% & 83.33 \% & 73.06 \% \\
1452 \hline
1453 4kB & 93.75 \% & 98.08 \% & 83.33 \% & 82.94 \% \\
1454 \hline
1455 8kB & 93.75 \% & 98.62 \% & 83.33 \% & 93.73 \% \\
1456 \hline
1457 16kB & 93.75 \% & 99.27 \% & 86.94 \% & 95.74 \% \\
1458 \hline
1459 32kB & 93.75 \% & 99.27 \% & 91.44 \% & 96.02 \% \\
1460 \hline
1461 64kB & 93.75 \% & 99.27 \% & 94.14 \% & 96.02 \% \\
1462 \hline
1463 128kB & 93.75 \% & 99.27 \% & 94.14 \% & 96.15 \% \\
1464 \hline
1465 \end{tabular}
1466 \caption{Hit rates for each set of texture coordinates and different cache sizes.}\label{tab:tcresults}
1467 \end{table}
1468
1469 \begin{figure}[htp]
1470 \centering
1471 \includegraphics[height=95mm]{tcresultsgraph.eps}
1472 \caption{Hit rates versus texel cache size. The X axis (cache size) uses a logarithmic scale.}
1473 \label{fig:tcresultsgraph}
1474 \end{figure}
1475
1476 Before we go on choosing a texel cache size, a few comments on these results can be made.
1477
1478 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$.
1479
1480 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.
1481
1482 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.
1483
1484 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.
1485
1486 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.
1487
1488 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.
1489
1490 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}:
1491 \begin{equation}
1492 \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}}}
1493 \end{equation}
1494
1495 We \textit{add} the hypothesis 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 tool chain. 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:
1496 \begin{equation}
1497 \left\lfloor \frac{H \cdot V-1}{N_{l}} \right\rfloor \not \equiv 0 \pmod{\frac{N_{c}}{N_{l}}}
1498 \end{equation}
1499 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.
1500
1501 \subsection{Bilinear filter}
1502 The bilinear filter is a straightforward arithmetic circuit that implements the equation~\ref{eq:bfilter} with five pipeline sub-stages.
1503
1504 \subsection{Write buffer}
1505 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.
1506
1507 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.
1508
1509 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.
1510
1511 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.
1512
1513 In the equations that follow, these symbols are used:
1514 \begin{itemize}
1515 \item $f$ is the system clock frequency in Hz.
1516 \item $w$ is the width of a FML word in bits.
1517 \item $n$ is the FML burst length.
1518 \item $\Delta_{w}$ is the memory write access time.
1519 \item $d$ is the number of bits per pixel.
1520 \item $T$ is the throughput of the write buffer, in pixels per second.
1521 \end{itemize}
1522
1523 We therefore have:
1524 \begin{equation}
1525 T = \frac{f \cdot n \cdot w}{d \cdot (\Delta_{w} + n)}
1526 \end{equation}
1527
1528 Thus, the write buffer can achieve a throughput of one pixel per clock cycle ($T = f$) if the memory write access time verifies:
1529 \begin{equation}
1530 \Delta_{w} \leq \frac{n \cdot w}{d} - n
1531 \end{equation}
1532
1533 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.
1534
1535 \begin{figure}[htp]
1536 \centering
1537 \includegraphics[height=95mm]{thwbufperf.eps}
1538 \caption{Theoretical write buffer throughput versus memory write access time.}
1539 \label{fig:thwbufperf}
1540 \end{figure}
1541
1542 \subsection{Control interface}
1543 \label{subsec:tmucsr}
1544 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.
1545
1546 \section{Extra features}
1547 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}):
1548 \begin{itemize}
1549 \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.
1550 \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.
1551 \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.
1552 \end{itemize}
1553
1554 \section{Implementation results}
1555 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.
1556
1557 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.
1558
1559 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 Mb/s on the memory system for scanning the frame buffer.
1560
1561 \begin{figure}[htp]
1562 \centering
1563 \includegraphics[height=75mm]{tmuresult.eps}
1564 \caption{Measured TMU performance versus global texel cache hit rate.}
1565 \label{fig:tmuresult}
1566 \end{figure}
1567
1568 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.
1569
1570 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:
1571 \begin{enumerate}
1572 \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}$.
1573 \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 de-interlacing}, 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}$.
1574 \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}$.
1575 \end{enumerate}
1576
1577 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.
1578
1579 \chapter{Floating point co-processor}
1580 \label{ch:pfpu}
1581 \section{Purpose}
1582 \label{sec:pfpupurpose}
1583 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.
1584
1585 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.
1586
1587 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!
1588
1589 We have therefore designed and implemented a co-processor for those computations, called PFPU (Programmable Floating Point Unit).
1590
1591 \section{Forms of parallelism}
1592 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}.
1593
1594 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.
1595
1596 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).
1597
1598 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.
1599
1600 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.
1601
1602 \section{Hardware architecture}
1603 \subsection{Overview}
1604 A fully software-based extraction of instruction-level parallelism was chosen for several reasons:
1605 \begin{itemize}
1606 \item Hardware-based extraction is more costly in terms of resources and more difficult to develop.
1607 \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.
1608 \item A software-based instruction scheduler can have a large instruction window, and thus extract more parallelism than an hardware solution could.
1609 \end{itemize}
1610
1611 This static scheduling technique makes the floating point co-processor 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}.
1612
1613 \begin{figure}[htp]
1614 \centering
1615 \includegraphics[height=100mm]{pfpu_architecture.eps}
1616 \caption{Hardware architecture of the floating point co-processor.}
1617 \label{fig:pfpuarch}
1618 \end{figure}
1619
1620 \subsection{Instruction set}
1621 The 25-bit PFPU instruction format is given in table~\ref{tab:pfpuinst}. The PFPU executes one such instruction per clock cycle.
1622
1623 \begin{table}
1624 \centering
1625 \begin{tabular}{|l|l|l|l|l|}
1626 \hline
1627 \textbf{Parameter} & Operand A & Operand B & Opcode & Destination \\
1628 \hline
1629 \textbf{Length} & 7 & 7 & 4 & 7 \\
1630 \hline
1631 \textbf{Bits} & \verb!24..18! & \verb!17..11! & \verb!10..7! & \verb!7..0! \\
1632 \hline
1633 \end{tabular}
1634 \caption{PFPU instruction format.}\label{tab:pfpuinst}
1635 \end{table}
1636
1637 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.
1638
1639 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).
1640
1641 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.
1642
1643 \subsection{Instruction RAM}
1644 The instruction RAM belongs on-chip for two simple reasons:
1645 \begin{itemize}
1646 \item it is small: it must only contain hundreds of instructions (the program for one vertex), so its capacity is only a few kilobytes.
1647 \item it transfers a large amount of data: one 25-bit instruction on each clock cycle at 100MHz yields a bandwidth of 2.5Gb/s.
1648 \end{itemize}
1649 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.
1650
1651 \subsection{ALU}
1652 \subsubsection{Overview}
1653 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.
1654
1655 The major pipelines of the ALU are listed below.
1656
1657 \subsubsection{Basic operations}
1658 The unit has pipelines that perform common operations: addition, subtraction, multiplication, absolute value and conversion between floats and two's complement integers.
1659
1660 \subsubsection{Inverse square root approximation}
1661 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}.
1662
1663 \subsubsection{Sine and cosine}
1664 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.
1665
1666 \subsubsection{Comparisons}
1667 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.
1668
1669 \subsubsection{Conditional statements}
1670 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.
1671
1672 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.
1673
1674 \section{Run-time compiler}
1675 \label{sec:pfpucomp}
1676 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}).
1677
1678 \subsection{Compilation into virtual machine instructions}
1679 \label{subsec:fpvm}
1680 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:
1681 \begin{itemize}
1682 \item It has the same operations and opcodes as the PFPU.
1683 \item Instructions complete and write their result to the register file in one cycle.
1684 \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.}
1685 \end{itemize}
1686
1687 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.
1688
1689 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.
1690
1691 \subsubsection{Sine and cosine}
1692 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:
1693 \begin{enumerate}
1694 \item Multiply by $\frac{8192}{2 \cdot \pi}$.
1695 \item Convert to integer.
1696 \item Look-up the sine or cosine value.
1697 \end{enumerate}
1698
1699 \subsubsection{Inverse square root}
1700 \begin{figure}
1701 \centering
1702 \begin{boxedminipage}{13cm}
1703 \begin{math}
1704 y \leftarrow \textrm{cast\_to\_float}(\textrm{0x5f3759df} - (\textrm{cast\_to\_integer}(x) >> 1)) \\
1705 y \leftarrow y \cdot (1.5 - 0.5 \cdot x \cdot y \cdot y)\textrm{ // first Newton-Raphson iteration} \\
1706 y \leftarrow y \cdot (1.5 - 0.5 \cdot x \cdot y \cdot y)\textrm{ // second iteration}
1707 \end{math}
1708 \end{boxedminipage}
1709 \caption{Fast inverse square root algorithm.}
1710 \label{fig:invsqrt}
1711 \end{figure}
1712
1713 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.
1714
1715 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}).
1716
1717 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.
1718
1719 \subsubsection{Square root}
1720 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.
1721
1722 \subsubsection{Inverse and division}
1723 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}$.
1724
1725 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}$.
1726
1727 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.
1728
1729 \subsection{Scheduling}
1730 \label{subsec:vliwsched}
1731 Once the complete code is available as FPVM instructions, the next step is to map these instructions to the PFPU and schedule them.
1732
1733 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:
1734 \begin{enumerate}
1735 \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.
1736 \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.
1737 \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.
1738 \item No output conflict. The instruction to be scheduled must not complete at the same cycle as another previously scheduled instruction.
1739 \end{enumerate}
1740 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.
1741
1742 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.
1743
1744 Several instructions can sometimes meet the conditions to be potentially scheduled 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.
1745
1746 \subsection{Constants and user variables}
1747 \label{subsec:constparam}
1748 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.
1749
1750 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.
1751
1752 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.
1753
1754 \section{Results}
1755 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.
1756
1757 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, ...).
1758
1759 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}).
1760
1761 \begin{table}
1762 \centering
1763 \begin{tabularx}{13cm}{|X|l|l|l|l|l|}
1764 \hline
1765 \textbf{Patch} & \textbf{Instructions} & \textbf{Cycles} & \textbf{CPI} \\
1766 \hline
1767 Default & 192 & 259 & 1.35 \\
1768 \hline
1769 Fvese - The Tunnel (Final Stage Mix) (simplified) & 208 & 286 & 1.38 \\
1770 \hline
1771 Geiss - Warp of Dali 1 & 220 & 292 & 1.33 \\
1772 \hline
1773 Krash - Digital Flame (simplified) & 216 & 293 & 1.36 \\
1774 \hline
1775 Unchained \& Rovastar - Wormhole Pillars (Hall of Shadows mix) & 231 & 326 & 1.41 \\
1776 \hline
1777 \end{tabularx}
1778 \caption{Greedy PFPU scheduler performance with the per-vertex math of different MilkDrop patches (Milkymist 0.5.1).}\label{tab:gfpusperf}
1779 \end{table}
1780
1781 \begin{table}
1782 \centering
1783 \begin{tabularx}{13cm}{|X|l|}
1784 \hline
1785 \textbf{Instruction} & \textbf{Latency} \\
1786 \hline
1787 Floating point addition & 4 \\
1788 \hline
1789 Floating point subtraction & 4 \\
1790 \hline
1791 Floating point multiplication & 5 \\
1792 \hline
1793 Floating point absolute value & 2 \\
1794 \hline
1795 Conversion from float to integer & 2 \\
1796 \hline
1797 Conversion from integer to float & 3 \\
1798 \hline
1799 Sine/cosine table look-up & 4 \\
1800 \hline
1801 Comparisons & 2 \\
1802 \hline
1803 Copy & 2 \\
1804 \hline
1805 Conditional & 2 \\
1806 \hline
1807 Inversion of the sign of operand 1 if operand 2 is negative & 2 \\
1808 \hline
1809 Inverse square root approximation & 2 \\
1810 \hline
1811 \end{tabularx}
1812 \caption{PFPU latencies in cycles (Milkymist 0.5.1).}\label{tab:pfpulatency}
1813 \end{table}
1814
1815 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.
1816
1817 \begin{table}
1818 \centering
1819 \begin{tabularx}{13cm}{|X|l|l|l|l|l|}
1820 \hline
1821 \textbf{Operation} & \textbf{Instructions} \\
1822 \hline
1823 Addition, subtraction, multiplication & 1 \\
1824 \hline
1825 Sine and cosine & 3 \\
1826 \hline
1827 Inverse square root & 11 \\
1828 \hline
1829 Square root & 12 \\
1830 \hline
1831 Division & 15 \\
1832 \hline
1833 \end{tabularx}
1834 \caption{Exact cost in instructions of common operations on the PFPU.}\label{tab:pfpucost}
1835 \end{table}
1836
1837 \chapter{Software}
1838 \label{ch:sw}
1839 \section{LatticeMico32}
1840 \label{sec:mico32}
1841 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 tool chain. It supports separate instruction and data caches with up to two ways. There are an optional barrel shifter, pipelined multiplier and multi-cycle divider.
1842
1843 \begin{figure}[htp]
1844 \centering
1845 \includegraphics[height=90mm]{lm32arch.eps}
1846 \caption{LatticeMico32 architecture (Lattice Semiconductor).}
1847 \label{fig:lm32arch}
1848 \end{figure}
1849
1850 The Milkymist system-on-chip uses LatticeMico32 with 2-way caches of 16kB each, and all the optional features enabled.
1851
1852 At the time this thesis is written, LatticeMico32 is the only hardware component that we have not developed specifically for the Milkymist project.
1853
1854 \section{Capabilities}
1855 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.
1856
1857 \begin{figure}[htp]
1858 \centering
1859 \includegraphics[height=100mm]{linux.eps}
1860 \caption{Linux booting on the Milkymist SoC.}
1861 \label{fig:linux}
1862 \end{figure}
1863
1864 \section{Benchmarking}
1865 The performance of the Milkymist SoC was compared to Microblaze~\cite{microblaze}, the proprietary Xilinx soft-core SoC platform.
1866
1867 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).
1868
1869 \begin{figure}[htp]
1870 \centering
1871 \includegraphics[height=100mm]{ml401.eps}
1872 \caption{Xilinx ML401 development board.}
1873 \label{fig:ml401}
1874 \end{figure}
1875
1876 All tests were run on a Xilinx ML401 (XC4VLX25 FPGA, see figure~\ref{fig:ml401}) development board, with a system frequency of 100MHz.
1877
1878 For Milkymist, the configuration used was the default one of the port to the ML401 board:
1879 \begin{itemize}
1880 \item Processor with hardware multiplier, divider and barrel shifter
1881 \item 16kB L1 instruction and data (write-through) cache (2-way set-associative)
1882 \item No memory management unit (LatticeMico32 does not have one)
1883 \item 16kB FML bridge write-back L2 cache (direct mapped)
1884 \item HPDMC DDR SDRAM controller, 32-bit SDRAM bus width
1885 \item 100MHz DDR SDRAM clock
1886 \item Video output running at standard VGA resolution, consuming approximately 300MBps of memory bandwidth
1887 \item Software: GCC 4.2.1 and Linux 2.6.23.
1888 \end{itemize}
1889
1890 For Microblaze, the configuration is as follows:
1891 \begin{itemize}
1892 \item Processor with hardware multiplier, divider and barrel shifter
1893 \item 16kB L1 instruction and data (write-through) cache (direct mapped, multi-way caches are not supported)
1894 \item Full memory management unit
1895 \item No L2 cache (not supported)
1896 \item MPMC DDR SDRAM controller, 32-bit SDRAM bus width
1897 \item 100MHz DDR SDRAM clock
1898 \item No video output
1899 \item Software: GCC 4.1.2 and Linux 2.6.32.4.
1900 \end{itemize}
1901
1902 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:
1903 \begin{equation}
1904 \frac{|t_{1}-t_{2}|}{\textrm{min}(t_{1}, t_{2})}
1905 \end{equation}
1906 It is meant to check that the results are deterministic and reproducible.
1907
1908 \begin{figure}[htp]
1909 \centering
1910 \includegraphics[height=75mm]{mm_vs_mb.eps}
1911 \caption{Comparative MiBench results of Milkymist and Microblaze.}
1912 \label{fig:mmvsmb}
1913 \end{figure}
1914
1915 \begin{table}
1916 \centering
1917 \begin{tabular}{|l|l|l|l|l|}
1918 \hline
1919 \textbf{Benchmark} & \textbf{Run 1} & \textbf{Run 2} & \textbf{Average} & \textbf{Deviation}  \\
1920 \hline
1921 jpeg & 2.57 s & 2.54 s & 2.56 s & 1.18 \% \\
1922 \hline
1923 mad & 5.84 s & 5.87 s & 5.86 s & 0.51 \% \\
1924 \hline
1925 tiff2bw & 9.51 s & 9.69 s & 9.6 s & 1.89 \% \\
1926 \hline
1927 tiffdither & 19.28 s & 19.3 s & 19.29 s & 0.10 \% \\
1928 \hline
1929 tiffmedian & 26.48 s & 26.26 s & 26.37 s & 0.84 \% \\
1930 \hline
1931 typeset & 21.44 s & 21.79 s & 21.62 s & 1.63 \% \\
1932 \hline
1933 \end{tabular}
1934 \caption{User execution times on Milkymist 0.2.}\label{tab:milkymistspeed}
1935 \end{table}
1936
1937 \begin{table}
1938 \centering
1939 \begin{tabular}{|l|l|l|l|l|}
1940 \hline
1941 \textbf{Benchmark} & \textbf{Run 1} & \textbf{Run 2} & \textbf{Average} & \textbf{Deviation}  \\
1942 \hline
1943 jpeg & 3.42 s & 3.58 s & 3.5 s & 4.68 \% \\
1944 \hline
1945 mad & 6.72 s & 7.11 s & 6.92 s & 5.80 \% \\
1946 \hline
1947 tiff2bw & 15.19 s & 14.12 s & 14.66 s & 7.58 \% \\
1948 \hline
1949 tiffdither & 24.72 s & 24.68 s & 24.7 s & 0.16 \% \\
1950 \hline
1951 tiffmedian & 35.02 s & 33.05 s & 34.04 s & 5.96 \% \\
1952 \hline
1953 typeset & 28.91 s & 28.83 s & 28.87 s & 0.28 \% \\
1954 \hline
1955 \end{tabular}
1956 \caption{User execution times on Microblaze 10.1.}\label{tab:microblazespeed}
1957 \end{table}
1958
1959 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.
1960
1961 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.
1962
1963 \section{Design of a MilkDrop-like rendering program}
1964 \subsection{Description}
1965 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}.
1966
1967 \begin{figure}[htp]
1968 \centering
1969 \includegraphics[width=\textwidth]{swarch.eps}
1970 \caption{Rendering software architecture.}
1971 \label{fig:swarch}
1972 \end{figure}
1973
1974 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.
1975
1976 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.
1977
1978 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.
1979
1980 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.
1981
1982 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.
1983
1984 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}.
1985
1986 Upon reception of the packet, the rendering loop takes its current frame, and runs the TMU (chapter~\ref{ch:tmu}) to distort it.
1987
1988 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.
1989
1990 Finally, the TMU is run twice to scale the internal frame buffer to the screen size and to apply the video echo.
1991
1992 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.
1993
1994 \subsection{Cache coherency}
1995 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.
1996
1997 \subsubsection{Cache coherency within the analysis loop}
1998 The only precaution that should be taken is to invalidate the L1 cache after each received buffer from the AC97 audio controller.
1999
2000 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-cache-able CSR address space.
2001
2002 The output the per-vertex equations is sent directly to the rendering loop.
2003
2004 \subsubsection{Cache coherency between the analysis and rendering loops}
2005 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.
2006
2007 \subsubsection{Cache coherency within the rendering loop}
2008 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:
2009 \begin{enumerate}
2010 \item Between the CPU and the TMU during the wave (and other elements) drawing process.
2011 \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.
2012 \end{enumerate}
2013
2014 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:
2015 \begin{enumerate}
2016 \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.
2017 \item Invalidating the L1 and L2 cache just after the wave drawing process.
2018 \end{enumerate}
2019
2020 \subsection{Event-driven operation}
2021 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.
2022
2023 \subsection{Results}
2024 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 developed.
2025
2026 \chapter{Conclusion and future works}
2027 \label{ch:conclusion}
2028 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.
2029
2030 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.
2031
2032 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.
2033
2034 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.
2035
2036 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.
2037
2038 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:
2039 \begin{enumerate}
2040 \item In order to be able to use more memory bandwidth from the SDRAM chips, an out-of-order memory controller could be designed.
2041 \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.
2042 \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.
2043
2044 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.
2045 \end{enumerate}
2046
2047 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.
2048
2049 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.
2050
2051 \begin{figure}[htp]
2052 \centering
2053 \includegraphics[width=\textwidth]{mm1.eps}
2054 \caption{Printed circuit board floor plan of the Milkymist One.}
2055 \label{fig:mm1}
2056 \end{figure}
2057
2058 \bibliography{thesis}{}
2059 \bibliographystyle{plain}
2060
2061 \end{document}