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