Copyright notices in docs
[mw/milkymist.git] / doc / confslides.tex
1 \documentclass{beamer}
2
3 \usepackage{beamerthemesplit}
4
5 \title{An open hardware VJ platform}
6 \subtitle{Technical aspects}
7 \author{S\'ebastien Bourdeauducq}
8 \date{December 2009}
9
10 \begin{document}
11
12 \frame{
13   \begin{figure}[H]
14   \includegraphics[height=18mm]{logo.eps}
15   \end{figure}
16   \titlepage
17 }
18
19 \section{Introduction}
20 \subsection{What we are speaking about}
21 \frame
22 {
23   \frametitle{What we are speaking about}
24 A device for video performance artists (VJs)...
25   \begin{itemize}
26   \item inspired by the popular MilkDrop program for PCs
27   \item with many interfaces: MIDI, DMX, can also do video mixing
28   \item highly integrated
29   \end{itemize}
30
31 At the frontier between...
32   \begin{itemize}
33   \item big computers with software to render visual effects
34   \item and small, handy microcontroller boards you connect to anything\\(``Arduino'' is today's buzzword for those)
35   \end{itemize}
36 }
37
38 \frame
39 {
40   \frametitle{What is that MilkDrop thing?}
41   \begin{figure}[H]
42   \includegraphics[height=58mm]{milkdrop1.eps}
43   \end{figure}
44 }
45
46 \frame
47 {
48   \frametitle{What is that MilkDrop thing?}
49   \begin{figure}[H]
50   \includegraphics[height=58mm]{milkdrop2.eps}
51   \end{figure}
52 }
53
54 \frame
55 {
56   \frametitle{What is that MilkDrop thing?}
57   \begin{figure}[H]
58   \includegraphics[height=58mm]{milkdrop3.eps}
59   \end{figure}
60 }
61
62 \subsection{Open Hardware, for real}
63 \frame
64 {
65   \frametitle{Open Hardware, for real}
66
67   \begin{itemize}
68   \item Arduino = AVR + power supply + connectors.
69   \item The AVR chip does all the magic! And it's a black box in every sense.
70   \item Here, all the logic of the chip is described (in Verilog HDL)...
71   \item ...and open source!
72   \item Ask Atmel for the same!
73   \end{itemize}
74 }
75
76 \frame
77 {
78   \frametitle{Truly Open Hardware projects}
79
80   \begin{itemize}
81   \item GRLIB/LEON3 (Aeroflex Gaisler, ESA)
82   \item OpenSPARC (Sun Microsystems)
83   \item Open Graphics
84   \item OpenPattern
85   \item Project VGA
86   \item ...and others
87   \end{itemize}
88 }
89
90 \section{How is MilkDrop working?}
91 \frame
92 {
93   \frametitle{How is MilkDrop working?}
94
95 Iterative rendering:
96   \begin{itemize}
97   \item Take the current image, and distort it
98   \begin{itemize}
99     \item zoom
100     \item rotation
101     \item scaling
102     \item others...
103   \end{itemize}
104   \item Draw waves and shapes
105   \item (In Milkymist: overlay some live video)
106   \item Display the result
107   \item Repeat the process!
108   \end{itemize}
109   (This is very simplified)
110 }
111
112 \frame
113 {
114   \frametitle{How is MilkDrop working?}
115
116   \begin{itemize}
117   \item Distortion and waves are controlled by fully customizable equations
118   \item The set of those equations is called a ``preset''
119   \item Similar to a ``patch'' in PureData
120   \item Interaction of the visuals with sound is defined by those equations
121   \item ...and also with DMX and MIDI in Milkymist
122   \end{itemize}
123 }
124
125 \section{Challenges}
126
127 \frame
128 {
129   \frametitle{Challenges}
130
131   \begin{itemize}
132   \item The need for a CPU
133   \begin{itemize}
134      \item flexibility
135      \item ease of reprogramming
136      \item ease of patching software bugs
137      \item software-friendly tasks: GUI, filesystems, protocols, ...
138   \end{itemize}
139   \item FPGA speed, size, and cost
140   \begin{itemize}
141      \item careful design
142      \item balance between hardware and software
143      \item software is cheap and slow, hardware is expensive and fast
144   \end{itemize}
145   \item Memory problems: bandwidth, size
146   \item Compute-intensive operations
147   \begin{itemize}
148      \item distorting the image
149      \item evaluating the equations
150   \end{itemize}
151   \end{itemize}
152 }
153
154 \section{System architecture}
155 \frame
156 {
157   \begin{center}
158   \framebox[100mm][c]{System architecture}
159   \end{center}
160 }
161
162 \frame
163 {
164   \frametitle{It contains a microcontroller!}
165   \begin{figure}[H]
166   \includegraphics[height=60mm]{microcontroller.eps}
167   \end{figure}
168 }
169
170 \frame
171 {
172   \frametitle{The design flow}
173   
174   ``System-on-a-Programmable-Chip'' (SoPC):
175   \begin{itemize}
176   \item A microcontroller is implemented using the FPGA fabric
177   \item The software is written and compiled (GCC)
178   \item The compiled firmware is flashed/loaded on the board
179   \item The microprocessor made from the FPGA fabric executes it
180   \item Acceleration units and specialty peripherals are added to the system and driven by the software
181   \end{itemize}
182 }
183
184 \section{Case studies}
185
186 \subsection{The memory problem}
187 \frame
188 {
189   \begin{center}
190   \framebox[100mm][c]{Case studies --- The memory problem}
191   \end{center}
192 }
193
194 \frame
195 {
196   \frametitle{The memory problem}
197   
198   \begin{itemize}
199   \item A tough one.
200   \item The application requires memory to be big, fast, and cheap at the same time.
201   \item The required memory size prohibits the use of SRAM
202   \item ...then we have to use DRAM and face all its problems.
203   \end{itemize}
204 }
205
206 \frame
207 {
208   \frametitle{How bad is it?}
209   
210   \begin{tabular}{|l|l|l|}
211   \hline
212   \textbf{Task} & \textbf{Bandwidth} & \textbf{Capacity} \\
213   \hline
214   VGA framebuffer, 1024x768, 75Hz, 16bpp & 900Mbps & 3MB \\
215   \hline
216   Distortion, 1024x768, 30fps, 16bpp & 720Mbps & -- \\
217   \hline
218   2xNTSC input, 720x576, 30fps, 16bpp & 380Mbps & 3MB \\
219   \hline
220   Software and misc. & 250Mbps & 16MB \\
221   \hline
222   \textbf{Total} & \textbf{2.2Gbps} & \textbf{22MB} \\
223   \hline
224   \end{tabular}\\
225   
226   \begin{itemize}
227   \item One DDR SDRAM chip running at 100MHz:\\(DDR-200 in marketingspeak)
228   \begin{itemize}
229   \item 3Gbps \underline{peak bandwidth}
230   \item 32MB capacity
231   \item a few dollars
232   \end{itemize}
233   \item This is still manageable!
234   \end{itemize}
235 }
236
237 \frame
238 {
239   \frametitle{Peak bandwidth?}
240   
241   Performance of SDRAM depends a lot on the cleverness of its controller. Example:
242   
243   \begin{figure}[H]
244   \includegraphics[height=30mm]{memlatency.eps}
245   \end{figure}
246   
247   In Milkymist, memory transfers are always done using bursts of 4 consecutive words (FML bus). The bus master caches or discards the data it does not want.
248 }
249
250 \frame
251 {
252   \frametitle{Bursts of 4 consecutive words: a good heuristics?}
253   
254   \begin{itemize}
255   \item Good for the VGA framebuffer (a big bandwidth consumer):
256   \begin{itemize}
257   \item when it gets a burst of 4 consecutive chunks from memory...
258   \item those chunks also represent consecutive pixels (in scan order)
259   \item ...so it can just put them in its output FIFO and easily acheive 100\% utilization!
260   \end{itemize}
261   \item It is the same for PAL/NTSC video inputs.
262   \item For image distortion: yes; more on this later.
263   \item For software: principle of temporal/spatial locality, caches.
264   \item And simplifies a lot (compared to a variable burst length):
265   \begin{itemize}
266   \item SDRAM controller design
267   \item Bus signaling
268   \item Bus arbitration
269   \item Cache controllers
270   \end{itemize}
271   \end{itemize}
272 }
273
274 \subsection{Distorting the image}
275 \frame
276 {
277   \begin{center}
278   \framebox[100mm][c]{Case studies --- Distorting the image}
279   \end{center}
280 }
281
282
283 \frame
284 {
285   \frametitle{What is ``distortion''?}
286   
287   \begin{figure}[H]
288   \includegraphics[height=40mm]{distortionsanofi.eps}
289   \end{figure}
290 }
291
292 \frame
293 {
294   \frametitle{More precisely...}
295   
296   \begin{itemize}
297   \item ``Texture mapping'' in OpenGL terminology
298   \item The MilkDrop preset equations define a mapping $f : (x,y)\rightarrow(X,Y)$
299   \item The point at $(x,y)$ in the source image should be at $(X,Y)$ in the destination image
300   \item Example: zoom by a factor of 2: $f(x,y) = (2 \cdot x, 2 \cdot y)$
301   \item Problem with pixels: how to fill the ``holes''?!
302   \item Tessellation, triangle strip
303   \end{itemize}
304 }
305
306 \frame
307 {
308   \frametitle{More precisely...}
309   \begin{itemize}
310   \item Tessellate the source image with triangles.
311   \item Apply the mapping to the vertices.
312   \item Fill the ``distorted'' triangles in the destination picture.
313   \item Interpolate linearly the source coordinates.
314   \end{itemize}
315   
316   \begin{figure}[H]
317   \includegraphics[height=35mm]{tesselsanofi.eps}
318   \end{figure}
319 }
320
321 \frame
322 {
323   \frametitle{Performance constraints}
324   
325   \begin{itemize}
326   \item To acheive 30fps at 1024x768, the Texture Mapping Unit (TMU) must process 24 million pixels per second.
327   \item With a 100MHz clock, we have 4 cycles to process a pixel.
328   \item With a naive implementation, each pixel requires (approx.):
329   \begin{itemize}
330   \item math: $\approx100$ cycles
331   \item one memory read: $\approx12$ cycles
332   \item one memory write: $\approx12$ cycles
333   \end{itemize}
334   \item Total: $\approx124$ cycles!!! Solutions for a $\approx3000\%$ speedup?!?
335   \end{itemize}
336 }
337
338 \frame
339 {
340   \frametitle{Solutions}
341   
342   \begin{itemize}
343   \item Improved algorithm
344   \begin{itemize}
345   \item Bresenham's linear interpolation algorithm
346   \end{itemize}
347   \item SIMD parallelism
348   \begin{itemize}
349   \item the same operation on independent data can be done in parallel
350   \item example: computing X and Y in the source image
351   \end{itemize}
352   \item Pipelined parallelism
353   \begin{itemize}
354   \item Milkymist's TMU has 14 pipeline stages
355   \item will grow as more features are added...
356   \item commercial GPUs can have hundreds
357   \end{itemize}
358   \item Smart memory access
359   \begin{itemize}
360   \item cache
361   \item write buffer
362   \end{itemize}
363   \end{itemize}
364 }
365
366 \frame
367 {
368   \frametitle{Solutions}
369   
370   \begin{itemize}
371   \item Let's focus on the memory read problem.
372   \begin{itemize}
373   \item others would need deep explanations of the algorithms.
374   \end{itemize}
375   \item Currently takes $\approx12$ cycles, and we have at most 4.
376   \item Use the bursts, and memorize them in a cache.
377   \end{itemize}
378   \begin{figure}[H]
379   \includegraphics[height=30mm]{memlatency.eps}
380   \end{figure}
381 }
382
383 \frame
384 {
385   \frametitle{Are bursts and cache a good idea?}
386   
387   Example: rotation of a triangle.
388   \begin{figure}[H]
389   \includegraphics[height=40mm]{tripattern.eps}
390   \end{figure}
391 }
392
393 \frame
394 {
395   \frametitle{How big should the cache be?}
396   \begin{figure}[H]
397   \includegraphics[height=38mm]{texelcache.eps}
398   \end{figure}
399   \begin{itemize}
400   \item Cache size: 4KB
401   \item Hit rate: 94\%
402   \item Average memory access time: 1.4 cycles
403   \item Problem solved!
404   \end{itemize}
405 }
406
407 \subsection{Evaluating MilkDrop equations}
408 \frame
409 {
410   \begin{center}
411   \framebox[100mm][c]{Case studies --- Evaluating MilkDrop equations}
412   \end{center}
413   \begin{itemize}
414   \item Some performance tricks are also used here
415   \item Floating-point hardware coprocessor (PFPU)
416   \item The main CPU compiles code on-the-fly for the coprocessor
417   \end{itemize}
418 }
419
420 \section{In practice}
421 \frame
422 {
423   \begin{center}
424   \framebox[100mm][c]{In practice}
425   \end{center}
426 }
427
428 \subsection{Development hardware}
429 \frame
430 {
431   \frametitle{Development board}
432   \begin{itemize}
433   \item Most developments were done on a Xilinx ML401 board.
434   \item Feature-rich.
435   \item Affordable: $\approx USD 500$.
436   \end{itemize}
437   \begin{figure}[H]
438   \includegraphics[height=40mm]{ml401.eps}
439   \end{figure}
440 }
441
442
443 \subsection{Development software}
444 \frame
445 {
446   \frametitle{Verilog simulations}
447   \begin{itemize}
448   \item Free simulators
449   \begin{itemize}
450   \item Icarus Verilog
451   \item GPL Cver
452   \item Verilator, innovative and amazingly fast, but currently buggy
453   \end{itemize}
454   \item Light-weight, run without a hitch on ultra-mobile laptops (EeePC)
455   \begin{itemize}
456   \item debug your Verilog code anytime and anywhere
457   \item try to do the same with Modelsim and FLEXnet licensing!
458   \end{itemize}
459   \item Expensive proprietary simulators from big EDA companies were not needed to develop Milkymist.
460   \end{itemize}
461 }
462
463 \frame
464 {
465   \frametitle{Logic synthesis}
466   \begin{itemize}
467   \item ISE Webpack from Xilinx.
468   \item Proprietary but free of charge.
469   \item Linux version.
470   \item Pretty good quality if you stick to command line.
471   \end{itemize}
472 }
473
474 \frame
475 {
476   \frametitle{Software development}
477   \begin{itemize}
478   \item CPU is supported by the GCC compiler (C/C++).
479   \item For debugging, software can be downloaded from RS232.
480   \end{itemize}
481   \begin{figure}[H]
482   \includegraphics[height=45mm]{serialdebug.eps}
483   \end{figure}
484
485 }
486
487
488 \section{Conclusion}
489 \frame
490 {
491   \frametitle{Conclusion}
492   \begin{itemize}
493   \item Wide availability of FPGAs opens new fields for hobbyists.
494   \item High-speed embedded computing, and applications.
495   \item This talk has presented a couple of high-performance logic design techniques.
496   \item I did not invent them. They are ubiquitous in the computer industry, but seldom heard of.
497   \end{itemize}
498 }
499
500 \frame
501 {
502   \frametitle{Thank you for your attention}
503   \begin{itemize}
504   \item Web: \url{http://www.milkymist.org}
505   \begin{itemize}
506   \item documented source code (GPLv3 licensing)
507   \item binary kits (to get started fast)
508   \item mailing list
509   \item wiki (with suggested contributions)
510   \item blog
511   \item these slides are online (GNU FDL licensing)
512   \end{itemize}
513   \item Mail: sebastien.bourdeauducq [AT] lekernel DOT net
514   \end{itemize}
515
516   \begin{center}
517   \framebox[100mm][c]{Questions?}
518   \end{center}
519 }
520
521 \end{document}