add diagrams
[libreriscv.git] / simple_v_extension / simple_v_chennai_2018.tex
1 \documentclass[slidestop]{beamer}
2 \usepackage{beamerthemesplit}
3 \usepackage{graphics}
4 \usepackage{pstricks}
5
6 \title{Simple-V RISC-V Extension for Vectorisation and SIMD}
7 \author{Luke Kenneth Casson Leighton}
8
9
10 \begin{document}
11
12 \frame{
13 \begin{center}
14 \huge{Simple-V RISC-V Extension for Vectors and SIMD}\\
15 \vspace{32pt}
16 \Large{Flexible Vectorisation}\\
17 \Large{(aka not so Simple-V?)}\\
18 \vspace{24pt}
19 \Large{[proposed for] Chennai 9th RISC-V Workshop}\\
20 \vspace{24pt}
21 \large{\today}
22 \end{center}
23 }
24
25
26 \frame{\frametitle{Credits and Acknowledgements}
27
28 \begin{itemize}
29 \item The Designers of RISC-V\vspace{15pt}
30 \item The RVV Working Group and contributors\vspace{15pt}
31 \item Allen Baum, Jacob Bachmeyer, Xan Phung, Chuanhua Chang,\\
32 Guy Lemurieux, Jonathan Neuschafer, Roger Brussee,
33 and others\vspace{15pt}
34 \item ISA-Dev Group Members\vspace{10pt}
35 \end{itemize}
36 }
37
38
39 \frame{\frametitle{Quick refresher on SIMD}
40
41 \begin{itemize}
42 \item SIMD very easy to implement (and very seductive)\vspace{10pt}
43 \item Parallelism is in the ALU\vspace{10pt}
44 \item Zero-to-Negligeable impact for rest of core\vspace{10pt}
45 \end{itemize}
46 Where SIMD Goes Wrong:\vspace{10pt}
47 \begin{itemize}
48 \item See "SIMD instructions considered harmful"
49 https://www.sigarch.org/simd-instructions-considered-harmful
50 \item Corner-cases alone are extremely complex.\\
51 Hardware is easy, but software is hell.
52 \item O($N^{6}$) ISA opcode proliferation!\\
53 opcode, elwidth, veclen, src1-src2-dest hi/lo
54 \end{itemize}
55 }
56
57 \frame{\frametitle{Quick refresher on RVV}
58
59 \begin{itemize}
60 \item Extremely powerful (extensible to 256 registers)\vspace{10pt}
61 \item Supports polymorphism, several datatypes (inc. FP16)\vspace{10pt}
62 \item Requires a separate Register File (32 w/ext to 256)\vspace{10pt}
63 \item Implemented as a separate pipeline (no impact on scalar)\vspace{10pt}
64 \end{itemize}
65 However...\vspace{10pt}
66 \begin{itemize}
67 \item 98 percent opcode duplication with rest of RV (CLIP)
68 \item Extending RVV requires customisation not just of h/w:\\
69 gcc and s/w also need customisation (and maintenance)
70 \end{itemize}
71 }
72
73
74 \frame{\frametitle{The Simon Sinek lowdown (Why, How, What)}
75
76 \begin{itemize}
77 \item Why?
78 Implementors need flexibility in vectorisation to optimise for
79 area or performance depending on the scope:
80 embedded DSP, Mobile GPU's, Server CPU's and more.\vspace{4pt}\\
81 Compilers also need flexibility in vectorisation to optimise for cost
82 of pipeline setup, amount of state to context switch
83 and software portability\vspace{4pt}
84 \item How?
85 By implicitly marking INT/FP regs as "Vectorised",\\
86 SV expresses how existing instructions should act
87 on [contiguous] blocks of registers, in parallel.\vspace{4pt}
88 \item What?
89 Simple-V is an "API" that implicitly extends
90 existing (scalar) instructions with explicit parallelisation
91 (i.e. SV is actually about parallelism NOT vectors per se)
92 \end{itemize}
93 }
94
95
96 \frame{\frametitle{What's the value of SV? Why adopt it even in non-V?}
97
98 \begin{itemize}
99 \item memcpy becomes much smaller (higher bang-per-buck)\vspace{10pt}
100 \item context-switch (LOAD/STORE multiple): 1-2 instructions\vspace{10pt}
101 \item Compressed instrs further reduces I-cache (etc.)\vspace{10pt}
102 \item greatly-reduced I-cache load (and less reads)\vspace{10pt}
103 \end{itemize}
104 Note:\vspace{10pt}
105 \begin{itemize}
106 \item It's not just about Vectors: it's about instruction effectiveness
107 \item Anything implementor is not interested in HW-optimising,\\
108 let it fall through to exceptions (implement as a trap).
109 \end{itemize}
110 }
111
112
113 \frame{\frametitle{How does Simple-V relate to RVV? What's different?}
114
115 \begin{itemize}
116 \item RVV very heavy-duty (excellent for supercomputing)\vspace{10pt}
117 \item Simple-V abstracts parallelism (based on best of RVV)\vspace{10pt}
118 \item Graded levels: hardware, hybrid or traps (fit impl. need)\vspace{10pt}
119 \item Even Compressed become vectorised (RVV can't)\vspace{10pt}
120 \end{itemize}
121 What Simple-V is not:\vspace{10pt}
122 \begin{itemize}
123 \item A full supercomputer-level Vector Proposal
124 \item A replacement for RVV (SV is designed to be over-ridden\\
125 by - or augmented to become, or just be replaced by - RVV)
126 \end{itemize}
127 }
128
129
130 \frame{\frametitle{How is Parallelism abstracted in Simple-V?}
131
132 \begin{itemize}
133 \item Register "typing" turns any op into an implicit Vector op\vspace{10pt}
134 \item Primarily at the Instruction issue phase (except SIMD)\\
135 Note: it's ok to pass predication through to ALU (like SIMD)
136 \item Standard (and future, and custom) opcodes now parallel\vspace{10pt}
137 \end{itemize}
138 Notes:\vspace{6pt}
139 \begin{itemize}
140 \item All LOAD/STORE (inc. Compressed, Int/FP versions)
141 \item All ALU ops (soft / hybrid / full HW, on per-op basis)
142 \item All branches become predication targets (C.FNE added)
143 \item C.MV of particular interest (s/v, v/v, v/s)
144 \end{itemize}
145 }
146
147
148 \frame{\frametitle{Implementation Options}
149
150 \begin{itemize}
151 \item Absolute minimum: Exceptions (if CSRs indicate "V", trap)
152 \item Hardware loop, single-instruction issue\\
153 (Do / Don't send through predication to ALU)
154 \item Hardware loop, parallel (multi-instruction) issue\\
155 (Do / Don't send through predication to ALU)
156 \item Hardware loop, full parallel ALU (not recommended)
157 \end{itemize}
158 Notes:\vspace{6pt}
159 \begin{itemize}
160 \item 4 (or more?) options above may be deployed on per-op basis
161 \item SIMD always sends predication bits through to ALU
162 \item Minimum MVL MUST be sufficient to cover regfile LD/ST
163 \item Instr. FIFO may repeatedly split off N scalar ops at a time
164 \end{itemize}
165 }
166 % Instr. FIFO may need its own slide. Basically, the vectorised op
167 % gets pushed into the FIFO, where it is then "processed". Processing
168 % will remove the first set of ops from its vector numbering (taking
169 % predication into account) and shoving them **BACK** into the FIFO,
170 % but MODIFYING the remaining "vectorised" op, subtracting the now
171 % scalar ops from it.
172
173 \frame{\frametitle{Predicated 8-parallel ADD: optimised (not masked)}
174 \begin{center}
175 \includegraphics[height=2.5in]{padd9_alu4.png}\\
176 {\bf \red Predicated adds are shuffled down: 4 in 1st cycle, 2 in 2nd}
177 \end{center}
178 }
179
180
181 \frame{\frametitle{Predicated 8-parallel ADD: 3 phase FIFO expansion}
182 \begin{center}
183 \includegraphics[height=2.5in]{padd9_fifo.png}\\
184 {\bf \red First cycle takes first four 1s; second takes the rest}
185 \end{center}
186 }
187
188
189 \frame{\frametitle{How are SIMD Instructions Vectorised?}
190
191 \begin{itemize}
192 \item SIMD ALU(s) primarily unchanged\vspace{10pt}
193 \item Predication is added to each SIMD element (NO ZEROING!)\vspace{10pt}
194 \item End of Vector enables predication (NO ZEROING!)\vspace{10pt}
195 \end{itemize}
196 Considerations:\vspace{10pt}
197 \begin{itemize}
198 \item Many SIMD ALUs possible (parallel execution)\vspace{10pt}
199 \item Very long SIMD ALUs could waste die area (short vectors)\vspace{10pt}
200 \item Implementor free to choose (API remains the same)\vspace{10pt}
201 \end{itemize}
202 }
203 % With multiple SIMD ALUs at for example 32-bit wide they can be used
204 % to either issue 64-bit or 128-bit or 256-bit wide SIMD operations
205 % or they can be used to cover several operations on totally different
206 % vectors / registers.
207
208 \frame{\frametitle{Predicated 9-parallel SIMD ADD}
209 \begin{center}
210 \includegraphics[height=2.5in]{padd9_simd.png}\\
211 {\bf \red 4-wide 8-bit SIMD, 4 bits of predicate passed to ALU}
212 \end{center}
213 }
214
215
216 \frame{\frametitle{What's the deal / juice / score?}
217
218 \begin{itemize}
219 \item Standard Register File(s) overloaded with CSR "vector span"\\
220 (see pseudocode slides for examples)
221 \item Element width and type concepts remain same as RVV\\
222 (CSRs are used to "interpret" elements in registers)
223 \item CSRs are key-value tables (overlaps allowed)\vspace{10pt}
224 \end{itemize}
225 Key differences from RVV:\vspace{10pt}
226 \begin{itemize}
227 \item Predication in INT regs as a BIT field (max VL=XLEN)
228 \item Minimum VL must be Num Regs - 1 (all regs single LD/ST)
229 \item SV may condense sparse Vecs: RVV lets ALU do predication
230 \item NO ZEROING: non-predicated elements are skipped
231 \end{itemize}
232 }
233
234
235 \begin{frame}[fragile]
236 \frametitle{ADD pseudocode (or trap, or actual hardware loop)}
237
238 \begin{semiverbatim}
239 function op_add(rd, rs1, rs2, predr) # add not VADD!
240  int i, id=0, irs1=0, irs2=0;
241  for (i = 0; i < VL; i++)
242   if (ireg[predr] & 1<<i) # predication uses intregs
243    ireg[rd+id] <= ireg[rs1+irs1] + ireg[rs2+irs2];
244 if (reg_is_vectorised[rd]) \{ id += 1; \}
245 if (reg_is_vectorised[rs1]) \{ irs1 += 1; \}
246 if (reg_is_vectorised[rs2]) \{ irs2 += 1; \}
247 \end{semiverbatim}
248
249 \begin{itemize}
250 \item SIMD slightly more complex (case above is elwidth = default)
251 \item Scalar-scalar and scalar-vector and vector-vector now all in one
252 \item OoO may choose to push ADDs into instr. queue (v. busy!)
253 \end{itemize}
254 \end{frame}
255
256 % yes it really *is* ADD not VADD. that's the entire point of
257 % this proposal, that *standard* operations are overloaded to
258 % become vectorised-on-demand
259
260
261 \begin{frame}[fragile]
262 \frametitle{Predication-Branch (or trap, or actual hardware loop)}
263
264 \begin{semiverbatim}
265 s1 = reg_is_vectorised(src1);
266 s2 = reg_is_vectorised(src2);
267 if (!s2 && !s1) goto branch;
268 for (int i = 0; i < VL; ++i)
269 if cmp(s1 ? reg[src1+i] : reg[src1],
270 s2 ? reg[src2+i] : reg[src2])
271 preg[rs3] |= 1 << i;
272 \end{semiverbatim}
273
274 \begin{itemize}
275 \item SIMD slightly more complex (case above is elwidth = default)
276 \item If s1 and s2 both scalars, Standard branch occurs
277 \item Predication stored in integer regfile as a bitfield
278 \item Scalar-vector and vector-vector supported
279 \end{itemize}
280 \end{frame}
281
282 \begin{frame}[fragile]
283 \frametitle{VLD/VLD.S/VLD.X (or trap, or actual hardware loop)}
284
285 \begin{semiverbatim}
286 if (unit-strided) stride = elsize;
287 else stride = areg[as2]; // constant-strided
288 for (int i = 0; i < VL; ++i)
289 if (preg_enabled[rd] && ([!]preg[rd] & 1<<i))
290 for (int j = 0; j < seglen+1; j++)
291 if (reg_is_vectorised[rs2]) offs = vreg[rs2][i]
292 else offs = i*(seglen+1)*stride;
293 vreg[rd+j][i] = mem[sreg[base] + offs + j*stride]
294 \end{semiverbatim}
295
296 \begin{itemize}
297 \item Again: elwidth != default slightly more complex
298 \item rs2 vectorised taken to implicitly indicate VLD.X
299 \end{itemize}
300 \end{frame}
301
302
303 \frame{\frametitle{Why are overlaps allowed in Regfiles?}
304
305 \begin{itemize}
306 \item Same register(s) can have multiple "interpretations"\vspace{6pt}
307 \item xBitManip plus SIMD plus xBitManip = Hi/Lo bitops\vspace{6pt}
308 \item (32-bit GREV plus 4x8-bit SIMD plus 32-bit GREV)\vspace{6pt}
309 \item RGB 565 (video): BEXTW plus 4x8-bit SIMD plus BDEPW\vspace{6pt}
310 \item Same register(s) can be offset (no need for VSLIDE)\vspace{6pt}
311 \end{itemize}
312 Note:\vspace{10pt}
313 \begin{itemize}
314 \item xBitManip reduces O($N^{6}$) SIMD down to O($N^{3}$)
315 \item Hi-Performance: Macro-op fusion (more pipeline stages?)
316 \end{itemize}
317 }
318
319
320 \frame{\frametitle{Why no Zeroing (place zeros in non-predicated elements)?}
321
322 \begin{itemize}
323 \item Zeroing is an implementation optimisation favouring OoO\vspace{8pt}
324 \item Simple implementations may skip non-predicated operations\vspace{8pt}
325 \item Simple implementations explicitly have to destroy data\vspace{8pt}
326 \item Complex implementations may use reg-renames to save power\\
327 Zeroing on predication chains makes optimisation harder
328 \end{itemize}
329 Considerations:\vspace{10pt}
330 \begin{itemize}
331 \item Complex not really impacted, Simple impacted a LOT
332 \item Overlapping "Vectors" may issue overlapping ops
333 \item Please don't use Vectors for "security" (use Sec-Ext)
334 \end{itemize}
335 }
336 % with overlapping "vectors" - bearing in mind that "vectors" are
337 % just a remap onto the standard register file, if the top bits of
338 % predication are zero, and there happens to be a second vector
339 % that uses some of the same register file that happens to be
340 % predicated out, the second vector op may be issued *at the same time*
341 % if there are available parallel ALUs to do so.
342
343
344 \frame{\frametitle{Predication key-value CSR store}
345
346 \begin{itemize}
347 \item key is int regfile number or FP regfile number (1 bit)\vspace{6pt}
348 \item register to be predicated if referred to (5 bits, key)\vspace{6pt}
349 \item register to store actual predication in (5 bits, value)\vspace{6pt}
350 \item predication is inverted (1 bit)\vspace{6pt}
351 \item non-predicated elements are to be zero'd (1 bit)\vspace{6pt}
352 \end{itemize}
353 Notes:\vspace{10pt}
354 \begin{itemize}
355 \item Table should be expanded out for high-speed implementations
356 \item Multiple "keys" (and values) theoretically permitted
357 \item RVV rules about deleting higher-indexed CSRs followed
358 \end{itemize}
359 }
360
361
362 \frame{\frametitle{Register key-value CSR store}
363
364 \begin{itemize}
365 \item key is int regfile number or FP regfile number (1 bit)\vspace{6pt}
366 \item treated as vector if referred to in op (5 bits, key)\vspace{6pt}
367 \item starting register to actually be used (5 bits, value)\vspace{6pt}
368 \item element bitwidth: default/8/16/32/64/rsvd (3 bits)\vspace{6pt}
369 \item element type: still under consideration\vspace{6pt}
370 \end{itemize}
371 Notes:\vspace{10pt}
372 \begin{itemize}
373 \item Same notes apply (previous slide) as for predication CSR table
374 \item Level of indirection has implications for pipeline latency
375 \end{itemize}
376 }
377
378
379 \frame{\frametitle{C.MV extremely flexible!}
380
381 \begin{itemize}
382 \item scalar-to-vector (w/no pred): VSPLAT
383 \item scalar-to-vector (w/dest-pred): Sparse VSPLAT
384 \item scalar-to-vector (w/single dest-pred): VINSERT
385 \item vector-to-scalar (w/src-pred): VEXTRACT
386 \item vector-to-vector (w/no pred): Vector Copy
387 \item vector-to-vector (w/src xor dest pred): Sparse Vector Copy
388 \item vector-to-vector (w/src and dest pred): Vector Gather/Scatter
389 \end{itemize}
390 \vspace{8pt}
391 Notes:\vspace{10pt}
392 \begin{itemize}
393 \item Really powerful!
394 \item Any other options?
395 \end{itemize}
396 }
397
398
399 \frame{\frametitle{Opcodes, compared to RVV}
400
401 \begin{itemize}
402 \item All integer and FP opcodes all removed (no CLIP!)\vspace{8pt}
403 \item VMPOP, VFIRST etc. all removed (use xBitManip)\vspace{8pt}
404 \item VSLIDE removed (use regfile overlaps)\vspace{8pt}
405 \item C.MV covers VEXTRACT VINSERT and VSPLAT (and more)\vspace{8pt}
406 \item VSETVL, VGETVL, VSELECT stay\vspace{8pt}
407 \item Issue: VCLIP is not in RV* (add with custom ext?)\vspace{8pt}
408 \item Vector (or scalar-vector) use C.MV (MV is a pseudo-op)\vspace{8pt}
409 \item VMERGE: twin predicated C.MVs (one inverted. macro-op'd)\vspace{8pt}
410 \end{itemize}
411 }
412
413
414 \frame{\frametitle{Under consideration}
415
416 \begin{itemize}
417 \item Is C.FNE actually needed? Should it be added if it is?
418 \item Element type implies polymorphism. Should it be in SV?
419 \item Should use of registers be allowed to "wrap" (x30 x31 x1 x2)?
420 \item Is detection of all-scalar ops ok (without slowing pipeline)?
421 \item Can VSELECT be removed? (it's really complex)
422 \item Can CLIP be done as a CSR (mode, like elwidth)
423 \item SIMD saturation (etc.) also set as a mode?
424 \item C.MV src predication no different from dest predication\\
425 What to do? Make one have different meaning?
426 \item 8/16-bit ops is it worthwhile adding a "start offset"? \\
427 (a bit like misaligned addressing... for registers)\\
428 or just use predication to skip start?
429 \end{itemize}
430 }
431
432
433 \frame{\frametitle{What's the downside(s) of SV?}
434 \begin{itemize}
435 \item EVERY register operation is inherently parallelised\\
436 (scalar ops are just vectors of length 1)
437 \item An extra pipeline phase is pretty much essential\\
438 for fast low-latency implementations
439 \item Assuming an instruction FIFO, N ops could be taken off\\
440 of a parallel op per cycle (avoids filling entire FIFO;\\
441 also is less work per cycle: lower complexity / latency)
442 \item With zeroing off, skipping non-predicated elements is hard:\\
443 it is however an optimisation (and could be skipped).
444 \end{itemize}
445 }
446
447
448 \frame{\frametitle{Is this OK (low latency)? Detect scalar-ops (only)}
449 \begin{center}
450 \includegraphics[height=2.5in]{scalardetect.png}\\
451 {\bf \red Detect when all registers are scalar for a given op}
452 \end{center}
453 }
454
455
456 \frame{\frametitle{TODO (break into separate slides)}
457
458 \begin{itemize}
459 \item Then explain why this proposal is a good way to \\
460 abstract parallelism\\
461 (hopefully also explaining how \\
462 a good compiler can make clever use of this increase parallelism\\
463 Then explain how this can be implemented (at instruction\\
464 issue time???) with\\
465 implementation options, and what these "cost".\\
466 Finally give examples that show simple usage that compares\\
467 C code\\
468 RVIC\\
469 RVV\\
470 RVICXsimplev
471 \end{itemize}
472 }
473
474
475 \frame{\frametitle{Summary}
476
477 \begin{itemize}
478 \item Designed for flexibility (graded levels of complexity)\vspace{6pt}
479 \item Huge range of implementor freedom\vspace{6pt}
480 \item Fits RISC-V ethos: achieve more with less\vspace{6pt}
481 \item Reduces SIMD ISA proliferation by 3-4 orders of magnitude \\
482 (without SIMD downsides or sacrificing speed trade-off)\vspace{6pt}
483 \item Covers 98\% of RVV, allows RVV to fit "on top"\vspace{6pt}
484 \item Not designed for supercomputing (that's RVV), designed for
485 in between: DSPs, RV32E, Embedded 3D GPUs etc.\vspace{6pt}
486 \item Not specifically designed for Vectorisation: designed to\\
487 reduce code size (increase efficiency, just
488 like Compressed)\vspace{6pt}
489 \end{itemize}
490 }
491
492
493 \frame{\frametitle{slide}
494
495 \begin{itemize}
496 \item \vspace{10pt}
497 \end{itemize}
498 Considerations:\vspace{10pt}
499 \begin{itemize}
500 \item \vspace{10pt}
501 \end{itemize}
502 }
503
504
505 \frame{
506 \begin{center}
507 {\Huge \red The end\vspace{20pt}\\
508 Thank you}
509 \end{center}
510 }
511
512
513 \end{document}