-
Notifications
You must be signed in to change notification settings - Fork 0
/
05-loops.tex
1178 lines (783 loc) · 54 KB
/
05-loops.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%% We use `subfiles' package
\documentclass[preamble.tex]{subfiles}
\begin{document}
\clearpage
\chapter{Generic loop representation and rates}
\label{ch:Loops}
\LiveFusion at the top level is a library of high level array combinators. Most of these conceptually represent a loop. Indeed, the user of the library can reason about the individual combinators as loops and consider the result of each to be an array.
However, when running the user's program, we are aiming to perform the required operations in as few loops as possible\footnote{This may increase register pressure. However, unless register spilling poses a problem in the future we favour the decreased memory traffic which is attained by array fusion.}. \todo{We have discussed the conditions for fusible combinators in Section ... In general, however...} Subject to certain restrictions, two combinators in \LiveFusion are fusible when the output array \*produced* by one combinator is \*consumed* as input by another combinator one element at a time from beginning to end.
In the \LiveFusion AST discussed in the previous chapter, this relationship is usually seen between a child node (the producer) and its parent node (the consumer). This is not true for \*random access* combinators like @backpermute@ which we discuss separately\todo{in Section }.
\todo{How do we know whether two combinators can be fused?}Intuitively, two combinators can be fused whenever one could write a loop by hand which would give the same final result for the same input as the two separate loops would.
%We need a way to programmatically determine whether a given pair of combinators can be replace with a semantically equivalent loop.
%The focus of this chapter is to establish the requirements for fusible combinators and define a loop representation to which such fusible combinators can be mapped.
The focus of this chapter is to establish a common loop representation to which fusible combinators can be mapped.
In the following sections we will look more closely at what a loop really is and then present the core of our fusion optimisation.
\clearpage
\section{Anatomy of a loop}
\label{sec:anatomy}
Despite the purely functional, combinatorial interface of the library, looking at a loop in a procedural way is the approach I have opted for in the middle layer of the system. It is represented by the \Loop language.\iloop
The loops \LiveFusion generates can be viewed as similar to those one might write in an Assembly language. It uses labelled basic blocks and has explicit control flow using @goto@ statements\footnote{The formal grammar of the \Loop language is introduced later in the chapter. It is presented in Figure \ref{fig:Loop-grammar} on page \pageref{fig:Loop-grammar}}.
However, as we will see later, the loops are more structured than those in \C and many other procedural languages. As such I urge the reader to think of them as being high-level and treat the explicit control flow as implementation details.
%The downside, however, is that our loop relies on @goto@-like statements whose use is almost always considered bad practice in modern software engineering.
Without further delaying the discussion of the matter we will now look at the structure of a typical @for@ loop in a language like \C in an attempt to shape our own loop structure.
\subsection{Structure of a \texttt{for} loop}
Consider the following fragment of a \C program that creates a new array @ys@, by applying some function @f@ to those elements of array @xs@ that satisfy some predicate function @p@ (in \Haskell this could be expressed as @ys = map f $ filter p $ xs@):
\begin{ccode}[numbers=left, label=lst:filterMapC]
double *ys = malloc(len * sizeof(double)); // result array
int j = 0; // output index
for(int i = 0; i < len; i++) {
if(p (xs[i])) {
ys[j] = f (xs[i]);
j++;
}
}
ys = realloc(ys, j * sizeof(double));
\end{ccode}
A @for@ loop in \C has four sections:
\begin{enumerate}
\halfspacing
\item \*initialisation* section (@i = 0@),
\item \*guard* section (@i < len@),
\item the main \*body* (@if ... @), and finally
\item the \*update* section (@i++@).
\end{enumerate}
Compared to free-formed @while@ loops which only have a @guard@ and a @body@, the @for@ loops are already much more structured.
However, as we see next, further structural elements could be introduced which will ultimately assist us when composing loops from array combinators.
\subsubsection{Initialisation}
The very first observation to make is that both the result array @ys@ and the output index @j@ were declared and initialised outside the @for@ loop.
In pursuit of a more structured and composable approach to looping all statements that are executed \*once* before the loop begins are placed in the \[init] basic block of the loop.
The initialisation code corresponds to the following in the \Loop language:
\begin{loopcode}
init:
let len = arrayLength xs
let ys = newArray len
let i = 0
let j = 0
goto guard
\end{loopcode}
\subsubsection{Guard}
The @guard@ section of a @for@ loop corresponds to the \[guard] block in the \Loop language. It can contain arbitrary statements but usually contains at least one @unless@ statement:
\begin{loopcode}[%
literate={_xs}{{\sub{xs}}}2,%
]
guard:
unless i < len | done
goto body_xs
\end{loopcode}
The @unless@ \*statement* transfers the control to a different block if the specified condition is \*false* (to \[done] in this case, the finaliser block discussed later). Otherwise the control stays in the current block, which in this case results in entering the loop's body.
\subsubsection{Update}
We defer presenting the \Loop language's equivalent of the @update@ section until after the structure of loop bodies is discussed shortly.
\subsubsection{Finalisation}
In the general case the @filter@ results in a shorter array than its input. Hence, after the @for@ loop finishes, the resulting array is \texttt{realloc}'ated to free the unused memory (in practice the array is unlikely to be copied).
This is one of the use cases for what is called the \[done] block of the loop:\todo{As we will see later it is not only useful for trimming and returning the final array but also for scheduling other loops such as in @append@ combinator.}.
\begin{loopcode}
done:
let result = sliceArray ys j -- resize to length j
return result
\end{loopcode}
As seen from the code, every loop has a result which it returns explicitly.
\subsection{``Dissecting loop bodies''}
\label{sec:dissecting-bodies}
We will now attempt to categorise the types of operations that all belong to the bodies of conventional @for@ and @while@ loops.
We continue using example presented on page \pageref{lst:filterMapC} as reference. In particular, the @body@ of the @for@ loop contained the following statements:
\begin{ccode}[numbers=left, firstnumber=4,]
if(p (xs[i])) {
ys[j] = f (xs[i]);
j++;
}
\end{ccode}
\subsubsection{Isolating combinators}
Line 5 of the @for@ loop, the statement @ys[j] = f (xs[i])@, is actually performing three operations:
\begin{enumerate}
\halfspacing
\item \*reading* an element from array @xs@,
\item \*producing* a new element by applying function @f@, and
\item \*writing* the new element into array @ys@.
\end{enumerate}
Recall, however, that we are trying to devise a loop representation for an application of fusion. When several combinators are fused into a single loop and produce no intermediate\iintermediate arrays, such reading and writing only happens at the beginning and at the end of a combinator pipeline\ipipe.
Hence we want to separate the notion of \*producing* a new element from the fact that it came from a physical array or just another computation. Likewise, we should not be concerned with how the new element is going to be consumed. It may or may not be written into a new array. It may or may not be used by a consuming combinator. However, it should not be up to an individual combinator to decide.
Each combinator in the pipeline is responsible to only take care of its own processing. In particular each combinator fills in its own \[body], \[yield] and \[bottom] basic blocks which we discuss next.
\subsubsection{Computing a new element in the \[body]}
As discussed previously, each combinator fills in a number of blocks with statements specific to it. For now we will only focus on the \[body] blocks produced:
\begin{loopcode}[%
literate=
{_xs}{{\sub{xs}}}2
{_filt}{{\sub{filt}}}2
{_map}{{\sub{map}}}3
]
body_xs:
let x = readArray xs i
body_filt:
unless (p x) | bottom_filt
body_map:
let y = f x
\end{loopcode}
The reading of @xs@ array is treated as a separate combinator and results in a @readArray@ statement. The \[body] of the @filter@ is a conditional jump if the predicate @p@ is not satisfied. Lastly, the \[body] of @map@ is the application of function @f@ to element @x@ and binding it to a fresh variable @y@.
We know however, that if @filter@ produces and element, then so does @map@. We say that @filter@ and @map@ produces elements at the same \term{rate}. Thus we can \*merge* the respective blocks of the two:
\begin{loopcode}[%
literate=
{_xs}{{\sub{xs}}}2
{_filt}{{\sub{filt}}}2
{_map}{{\sub{map}}}3
]
body_xs:
let x = readArray xs i
body_filt/_map:
unless (p x) | bottom_filt
let y = f x
\end{loopcode}
It was mentioned that each combinator also introduces \[yield] and \[bottom] blocks.
The complete \Loop generated for @ys = map f $ filter p $ xs@ as well as its control flow graph (CFG)\icfg are shown on Figure~\ref{fig:MapFilterLoop}. In addition to \[init], \[guard], \[body] and \[done] blocks it also contains \[yield] and \[bottom] block with the required control flow. A step-by-step explanation of these spans the following four sections.
\subsubsection{Yielding produced elements}
The \Loop language attempts to be precise as to where the element is produced and where it is consumed. More concretely, the \[yield] block of the loop is only ever entered if an element has been produced in the current iteration.
\begin{bluebox}
The \[body] block contains the code that is concerned with producing an element, however an element is known to have been produced only if the control reaches the \[yield] block.
\end{bluebox}
Every \[body] block on the listing is accompanied by the \[yield] block. The combinator reading the @xs@ array in \[body$_{xs}$] produces an element @x@ at every iteration, hence the corresponding \[yield$_{xs}$] block is entered unconditionally.
On the other hand, the @filter@ (and the subsequent @map@) may skip an element hence the possibility possibility of bypassing \[yield$_{filt/map}$] block.
This allows us to make assumptions about the behaviour of a loop without knowing what the loop is doing internally.
\subsubsection{Writing an element into result array}
The separation of \[yield] and \[body] has allowed for a finer grained loop structure.
In particular, if the result of a combinator has to be materialised into the physical array (as in the the case of @map@ in our example), the @writeArray@ statement needs to be inserted into \[yield$_{map}$]:
\begin{hscode}
writeArray ys j y -- write element y into array ys at index j
\end{hscode}
\subsubsection{Updating index}
The \[yield] block also provides a convenient place to update the index variable.
In our example the loop contains two \*rates*\irate:
\begin{itemize}
\halfspacing
\item one at which the elements are read from the source array,
\item and one at which the elements of @filter@ and @map@ are produced
\end{itemize}
With the current loop structure, updating both @i@ and @j@ index is a matter of placing an increment statement in the right \[yield] block:
\begin{loopcode}[%
literate=
{_xs}{{\sub{xs}}}2
{_filt}{{\sub{filt}}}2
{_map}{{\sub{map}}}3
]
yield_xs:
i := i + 1
goto body_filt
yield_filt/_map:
writeArray ys j y
j := j + 1
goto bottom_map
\end{loopcode}
As seen in the code above \Loop language supports destructive updates through using @assignment@ (@:=@).
This introduction of the index update is uniform for all \*rates* that may be present in the loop. This is in contrast to the @for@ loop originally presented on page \pageref{lst:filterMapC} where @i++@ was part of @update@ section, while @j++@ was inside the @for@ loop's body.
\subsubsection{Ending the iteration}
When the iteration has finished the last block that is entered \*unconditionally* (for each rate) is \[bottom]. In the given examples the two \[bottom] blocks simply transfer the control to the beginning of the next iteration, the \[guard]. However, in more sophisticated loops, e.g. @append@ combinator\todo{\ref{sec:append}}, the \[bottom] blocks may serve other purposes.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Final Loop for mapFilter example.
\begin{figure}
\begin{subfigure}{.6\textwidth}
\begin{loopcode}[%
literate=
{_xs}{{\sub{xs}}}2
{_filt}{{\sub{filt}}}2
{_map}{{\sub{map}}}3
]
init:
let len = arrayLength xs
let ys = newArray len
let i = 0
let j = 0
goto guard
guard:
unless i < len | done
goto body_xs
body_xs:
let x = readArray xs i
goto yield_xs:
yield_xs:
i := i + 1
goto body_filt
body_filt/_map:
unless (p x) | bottom_filt
let y = f x
goto yield_map:
yield_filt/_map:
writeArray ys j y
j := j + 1
goto bottom_map
bottom_filt/_map:
goto bottom_xs
bottom_xs:
goto guard
done:
let result = sliceArray ys j
return result
\end{loopcode}
\end{subfigure}%
%
\begin{subfigure}[right]{.4\textwidth}
\includegraphics[center,scale=\omniscale]{img/CFG-MapFilter}
\end{subfigure}
\caption{Internal \Loop language representation for \code{ys = map f $ filter p $ xs} (left) and the corresponding CFG (right).}
\label{fig:MapFilterLoop}
\end{figure}
\subsection{Summary of loop structure}
\label{sec:anatomy-summary}
In summary the common loop structure to be used throughout this chapter\footnote{At least until segmented combinators are introduced.\todo{in ref}} is comprised of the following 6 loop sections, represented by basic blocks in the \Loop language:\iblock
\begin{enumerate}
\item \[init] block is the main entry into the loop and contains statements which need to execute only once for the whole loop. New array allocation, index and length variable initialisation all belong here.
\item \[guard] block performs looping condition tests before every iteration of the loop.
\item \[body] block contains all statements concerned with reading arrays and computing elements. This block is \*rate*-specific and there is a new \[body] block for every distinct rate in the loop.
\item \[yield] block for a particular rate is entered only if a \*new element* has been produced by the \[body] block of the same rate in the current iteration. It is not entered if the loop's logic has skipped to the next iteration without producing an element (e.g. in @filter@ combinator). This is the place to update the loop index as well as \*write* the produced element in the resulting array if required.
\item \[bottom] block is entered unconditionally at the end of every iteration whether of not an element has been produced. Uses beyond going back up to the beginning of the next iteration will be seen later in this chapter.
\item \[done] block performs any remaining operations after the loop has finished. In particular it returns the final result from the loop. Unlike the loops in the majority of procedural languages the @return@ of values \*from a loop* is explicit in the \Loop language.
\end{enumerate}
Figure~\ref{fig:CFG-basic} shows the default control flow between these sections.
\begin{figure}[h!]
\includegraphics[center,scale=\omniscale]{img/CFG-basic}
\caption{Default control flow between basic blocks in the \Loop language.}
\label{fig:CFG-basic}
\end{figure}
\clearpage
\section{The \Loop language more formally}
\label{sec:The-Loop-language}
\iloop
So far we have used the following features of the \Loop language:
\begin{enumerate}
\halfspacing
\item New variable binding (@i = 0@)
\item Variable assignment (@i := i + 1@)
\item Explicit control transfer (@goto body@)
\item Conditional control transfer (@unless i < len | done@)
\item Returning values from loop (@return ys'@)
\item A number of built-in array primitives: (@newArray@, @readArray@, @writeArray@, @arrayLength@ and @sliceArray@).
\end{enumerate}
All of the above are \*statements*, which are grouped into labelled \*basic blocks*.\iblock
The grammar of the \Loop language is presented formally in Figure~\ref{fig:Loop-grammar}. The syntax seen in the examples throughout this thesis is the same as used by the pretty printer for the language and it faithfully\footnote{I have taken the liberty of rewriting operators in infix notation and omitting explicit literal conversions such as \code{fromInteger 1}.} reproduces the internal representation of \Loop programs.
\begin{figure}[htpb]
\subfile{loop-grammar}
\caption{\label{fig:Loop-grammar}Grammar of \Loop language.}
\end{figure}
\todo{Put the footnotetext on the same page where the grammar ends up}
\footnotetext{For improved readability the unique integers are replaced with meaningful names in the code listings. \*(Footnote for listing \ref{fig:Loop-grammar})*}
If the grammar is studied more carefully one would note that one basic block may have multiple associated labels. We have seen a use case for this when we merged \[body], \[yield] and \[bottom] basic blocks of @filter@ and @map@ combinators (Figure~\ref{fig:MapFilterLoop}). Such merged blocks can be referenced by either label. For example, \[bottom\sub{filt/map}] was being referenced both by \[bottom\sub{filt}] and \[bottom\sub{map}].
It should also be noted that each label and variable in the language is postfixed with a unique value which has so far been omitted from the listings. However, \[body\sub{xs}] is an example of such label identification. At the implementation level these values are unique integers. However, for improved readability they are replaced with combinator names and other meaningful identifiers.
Being a flexible assembly-style language, the \Loop language is not limited by the basic block structure discussed in Section~\ref{sec:anatomy} and summarised in Section~\ref{sec:anatomy-summary}. However, as seen in the rest of this chapter this structure has proven to be a useful common base for many types of arrays combinators. Thus we assume this to be the common pattern of using the \Loop language.
Semantically, the \Loop language does not presume a fixed order of evaluating @let@ bound variables. However, all statements affecting control flow (@goto@, @unless@, @if@) are executed in the order they appear in the block.
% Lastly, the new value of assigned variables ($\coleq$) is not available until the next block the control is transferred to. This is an implementation side-effect of the \*liveness analysis* pass (Section~\ref{sec:Liveness-analysis}) which however is helpful in implementing fused loops.
\clearpage
\section{Fused loops generation}
\label{sec:loop-generation}
In the previous section we have seen the first example of the \Loop EDSL which computed a @filter@ of an array followed by a @map@. We have also identified five main \*sections* of a loop, represented by \*basic blocks* in the \Loop language: \[init], \[guard], \[body], \[yield], \[bottom] and \[done].
We shall revisit the example from the previous section and introduce the process by which a \Loop is generated.
This time we extend the example with specific functions passed to @map@ and @filter@ combinators. The function @toPercentages@ shown on Figure~\ref{fig:toPercentages} (left) converts an array of fractions to their percentage equivalents, filtering out those below $0.01$ (or $1\%$).
\begin{figure}
\begin{subfigure}{.66\textwidth}
\begin{hscode}
toPercentages :: Array Double -> Array Double
toPercentages fractions
= let significant = filter (>=. 0.01) fractions
percents = map (* 100) significant
in percents
\end{hscode}
\end{subfigure}%
%
%\begin{subfigure}{.3\textwidth}
% \includegraphics[height=12em]{img/toPercentages-flow}
%\end{subfigure}
%
\begin{subfigure}{.34\textwidth}
\includegraphics[scale=\omniscale]{img/AST-toPercentages}
\end{subfigure}
\caption{\code{toPercentages} function (left) and its \LiveFusion AST (right).}
\label{fig:toPercentages}
\end{figure}
\subsection{Start with an AST}
The @toPercentages@ function internally uses a pipeline of two combinators: the output array of @filter@ (called @significant@) becomes the input array of @map@. Recalling that @Array Double@ is the type synonym for @AST (Vector Double)@, each combinator constructs a node in an AST representing a \*delayed array computation*.
It is not known statically if the input array, @fractions@, is computed by a pipeline of combinators or whether it is a @Manifest@ array stored in memory. Likewise, it is not known before runtime if the resulting @percents@ array is consumed by another combinator and the pipeline of delayed operation will continue to grow after @toPercentages@ function returns.
For the purposes of illustrating a complete running example we will assume that the @toPercentages@ function is called with a @Manifest@ array as argument and the result is immediately \*forced* to be computed (e.g. to be written out to a file or to be consumed in a random access fashion).
In this case the AST shown on Figure~\ref{fig:toPercentages} (right) is constructed and \*forced* to a @Manifest@ array at the runtime of the program:
\begin{hscode}
-- AST that may be a result of a call to toPercentages
ast :: AST (Vector Double)
ast = force
$ Map (* 100)
$ Filter (>=. 0.01)
$ Manifest vec
-- LiveFusion library functions
force :: Elt a => AST (Vector a) -> AST (Vector a)
force = Manifest . evalAST
evalAST :: AST a -> a
evalAST = ... -- compile AST and compute result
\end{hscode}
The three fusible combinators represented by @Manifest@, @Filter@ and @Map@ AST nodes are followed by the call to an evaluator, which processes them individually as shown next.
% After sharing recovery each AST node (or rather ASG node) is assigned a unique value
\subsection{Generate loops for individual combinators}
\label{sec:individual-loops}
In order to generate the \Loop language code for an AST of combinators, the evaluator first processes combinators individually. For each combinator it populates the sections of the loop that were identified in Section~\ref{sec:anatomy}. It does so by inserting new statements into the appropriate basic blocks of a loop template.
\subfile{lst-toPercentages-loops}
The left of Figure~\ref{fig:toPercentages-loops} shows the loops generated for the individual combinators. The figure is implicitly referenced in the following discussion.
All variables and labels introduced by a particular combinator are given a unique identifier. In listings these are: \*mfst* (short for \*Manifest*), \*map* or \*filt*.
Internally however, the library uses unique integers to distinguish between similarly named variables and labels belonging to different combinators (e.g. @body_2@ and @elt_3@). This not only avoids variable name clashes, but as we discuss next, enables communication among combinators through naming conventions.
\subsubsection{Iterate over manifest array}
\label{sec:manifest}
Recalling that the @Manifest@ combinator is the only combinator in the pipeline that holds a reference to the physical array, its loop does nothing more than to read the array @arr@\sub{mfst} element by element.
It is worth noting that the array is not @let@-bound in any of the blocks. This is due to the fact that the array is an \*argument* to the loop and is passed from the running program when the computation is finally ready to be performed (code generation and loading are discussed in Chapter~\ref{ch:Code-Generation}).
The combinator introduces a length variable @len@\sub{mfst} which it binds in loop initialisation block @init@\sub{mfst}.
The result of array read is placed in @elt@\sub{mfst} variable.
Notably, the combinator does not bind the index variable @ix@\sub{mfst} itself but assumes that it's present in scope. The insertion of appropriate index variables is done after the complete loop is analysed and all \*rates* are established.\todo{as discussed in ref}
\subsubsection{Filter}
In the partial loop representing the @filter@ combinator, all bound variables and label names are identified by \*filt*.
As discussed previously in Section~\ref{sec:Scalar-language} it is essential for performance that the user functions parametrising combinators be inlined in the generated code. In case of the @filter@ the predicate function $(\geq 0.01)$ has been inlined as the predicate expression to the @unless@ statement.
While the length of output array of @filter@ may be different from the length of input, the \*upper bound* on the length is the same as that of the previous combinator. This is expressed by binding the length variable @len@\sub{filt} to @len@\sub{mfst} of the @Manifest@ combinator.
Similarly, the resulting element @elt@\sub{filt} is bound to be @elt@\sub{mfst} -- the output of @Manifest@ in the same iteration of the loop.
\subsubsection{Map}
Populating the loop with @map@-specific statements is straight-forward.
Since the length of the output of @map@ is always the same as the length of input, the @len@\sub{map} variable is simply rebound. This also means that @Manifest@, @filter@ and @map@ share the same \*upper bound* on the length of their output arrays. %This means that @Manifest@ combinator uses one index, while both @filter@ and @map@ are using another. This supports the \*rate*-changing\irate nature of @filter@.
To compute @elt@\sub{map} for the current iteration, we only need to know @elt@\sub{filt}, that is the element produced by the previous combinator \*in the current iteration*.
Again, the user specified function $(* 100)$ is inlined to facilitate generation of fast code.
\subsubsection{Physical array creation}
For the @toPercentages@ example we said the pipeline of combinators will be forced to a @Manifest@ array immediately after the @map@.
The statements required to allocate, populate, slice and return the new array are self-explanatory.
It is worthy of note that the design decision to transfer control to \[yield] basic block only when an element is produced has made it very easy to introduce the array write.
\subsection{Rates and looping}
\label{sec:rates}\irate
Multiple times throughout this thesis, the concept of \term{rates} has been mentioned.
\begin{bluebox}
\term{Rate} is a property of a combinator within a combinator graph. If two combinators are statically known to produce arrays of the same length, they are said to have the same \term{rate}.
\end{bluebox}
For example, all three @map@s in @map h . map g . map f@ are known to share the same rate since their inputs and outputs will be of the same length.
For the same reason the @filter@ and the subsequent @map@ of the @toPercentages@ example share the same rate since they both produce same-length arrays. As such, they are assigned a single index variable @ix@\sub{filt} (Figure~\ref{fig:toPercentages-loops}).
However, the @filter@ combinator has earlier been identified as \*rate-changing*. In particular we treat @filter@ as a combinator producing elements at a \term{subrate} of the previous combinators. In the @toPercentages@ example, the @filter@ was preceded by @Manifest@, which receives it's own separate index variable @ix@\sub{mfst}.
\begin{bluebox}
If the rates of combinators are equal they share one index variable and their corresponding blocks can be merged together.
If a combinator runs at a \*subrate* of another combinator then it has its own \[body], \[yield] and \[bottom] blocks since it may not produce an element at every iteration.
\end{bluebox}
Rate equality and subrate relationship are not the only possible relationships between two combinators. We will introduce other relationships when we discuss segmented combinators in Section~\ref{sec:Loops-segmented-combinators}.
\subsection{Naming conventions}
\label{sec:naming-conventions}
As seen from the loop code generated for the individual combinators in the @toPercentages@ example, the \Loop language uses a set of \*naming conventions* to facilitate communication between consecutive combinators in a pipeline. In particular the following are always true for a combinator with identifier \*id*:
\begin{itemize}
\halfspacing
\item Variable @elt@\sub{id} contains the value of produced element at every iteration
\item Variable @len@\sub{id} contains the upper bound on the length of the output array
\item Variable @ix@\sub{id} contains the index of the element being produced.
\end{itemize}
Binding @elt@\sub{id} and @len@\sub{id} in every combinator ensures that this information is \*propagated* upwards through the pipeline of combinators. In particular, the @filter@ only required to know the \*id* of @Manifest@ combinator below it to infer these variables.
\begin{bluebox}
By design the combinators know their own unique identifiers and the unique identifiers of the combinators they are referencing and nothing else.
\end{bluebox}
\subsection{Merging loops}
We have given the \Loop language representations for @Manifest@, @map@ and @filter@ combinators as well as the code that writes out physical arrays.
In order a create a succinct loop, these individual loops are merged into one loop.
%In order a create one succinct loop, these individual loops are merged into one loop as they are being created. Each combinator has access to the loop composed by all of the combinators below it. For example, when fusing the @map@ the cumulative loop of both @filter@ and @Manifest@ is available for it to be merged with.
For combinators as simple as @map@ and @filter@ merging loops means to simply merge the statements of the corresponding blocks blocks in no particular order.
As seen from the final loop on Figure~\ref{fig:toPercentages-loops} (right), not only the statements of same rate blocks have been merged together, but also their labels: each block can now be identified by one more of the three identifiers (e.g. @body@\sub{filt/map} can be identified by either \*filt* or \*map* identifier).
This is done in order to support fusing complex ASTs with many shared nodes. The benefit of this may appear much clearer when we introduce nested combinators in Section~\ref{sec:Loops-segmented-combinators}.
We will now briefly discuss the mechanism by which this is done.
\subsubsection{Managing label sets with \name{AliasMap}}
In order to achieve the flexibility of having multiple labels associated with the same block I have implemented a new type of associations map called \name{AliasMap}.
It offers a familiar interface (Listing~\ref{lst:AliasMap-interface}) similar to that of \Haskell's @Data.Map@. The difference is that it allows for a \*set* of keys to be associated with one value. In addition to the usual functions found in @Data.Map@ one can query the map using \*synonyms*. That is, a value can be retrieved from the map given any key associated with that value.
The notion of \*key synonyms* is used throughout \name{AliasMap} interface which greatly facilitates managing and merging loops where blocks are associated with multiple labels.
\lstinputlisting[style=haskell, float, caption={\name{AliasMap} interface (partial). \code{Ord k} constraints omitted for brevity.}, label=lst:AliasMap-interface]{listings/AliasMap-interface.hs}
\clearpage
\section{More on \texttt{goto}s}
While the use of @goto@s is considered bad practice in modern software engineering I note several reasons for using them in the \Loop intermediate language:
\begin{itemize}
\item It is completely hidden from the library user.
Given a well behaving \Loop code generator the produced code will always be valid if the user program is valid.
This is akin to using @unsafePerformIO@ and the like within the library internals for performance reasons. They can lead to bad code but with careful use result in very noticeable performance gains in purely functional programs.
\item The \Loop language was designed with a pluggable backend in mind.
It was assumed that assembly-like \Loop language would be easier to connect with any backend.
Specifically in the \Haskell backend, @goto@ statements are translated to tail-recursive function calls.
An \LLVM backend is also planned. \LLVM uses a very similar notion of \*basic blocks*.
\item The @goto@ based design was the most flexible and the easiest to implement.
Nonetheless, this does not prevent the \Loop language from being extended to support a safer programming model.
\end{itemize}
\clearpage
\section{Flat array combinators}
\label{sec:Loops-flat-combinators}
\todo{Intro to the section. Say it's going to be brief. \ref{fig:CFG-basic}}
\subsection{Reductions}
We have already looked at how the indices maintain the state of the loop between iterations. Although it is probably the most obvious state a loop has, it is not the only one. Perhaps the most prominent standard list combinators that pass partial results to recursive calls as accumulators are @fold@s and @scan@s. \LiveFusion also offers these combinators.
In practice, binding and using accumulator variables like this in the \Loop language is straight-forward and is no different from binding and using index variables. They are both treated as mutable variables in the \Loop language.
Suppose, we wanted to translate @scan (*) 0 xs@ to a loop. As discussed previously in Section~\ref{sec:naming-conventions} on naming conventions the generation of loop blocks for @scan@ proceeds in assumption that variables @len@\sub{xs} and @elt@\sub{xs} are in scope.
The following is the portion of the loop generated for @scan@ combinator:
\begin{loopcode}[%
literate=
{_1}{{\sub{scan}}}3
{_3}{{\sub{xs}}}1,
]
init_1/_3:
let len_1 = len_3
let z_1 = 1
let acc_1 = z_1
body_1/_3:
let elt_1 = acc_1
bottom_1/_3:
acc_1 := acc_1 * elt_3
\end{loopcode}
Generating loop code for @fold@ is very similar except no element @elt@\sub{fold} is produced in each iteration and the final result is stored in @acc@\sub{fold}.
\subsection{Zipping}
\label{sec:zipping}
So far the combinator pipelines we have looked at had a list like structure. Each combinator would consume exactly one array and produce another. However, for many programs this is not sufficient. Many combinators take multiple arrays as input.
In general there is no constraint on how a combinator would consume each of those arrays. Some combinators (e.g. @backpermute@) require that one of the argument arrays can be accessed randomly. In other cases, combinators like @append@ and @interleave@ consume arrays independently (not in a lock step).
However, there are combinators like @zipWith@$N$ which consume $N$ arrays in lock step.
A call to @zipWith (*) xs ys@ element-wise multiplies @xs@ and @ys@. Those two arrays may internally be pipelines of combinators. It results in the following \Loop code:
\begin{loopcode}[%
literate=
{_1}{{\sub{zip}}}2
{_2}{{\sub{xs}}}1
{_3}{{\sub{ys}}}1,
]
init_1/_2/_3:
let len_1 = len_2
body_1/_2/_3:
let elt_1 = elt_2 * elt_3
\end{loopcode}
The code is similar to that of @map@ (Figure~\ref{fig:toPercentages-loops}). In fact @zipWith@$N$ combinators can be viewed as generalised @map@s.
There are two problems with @zipWith@$N$ family of combinators:
\begin{enumerate}
\item The lengths of @xs@ and @ys@ may be different.
\item The loops for @xs@ and @ys@ may not produce elements in every iteration.
\end{enumerate}
Appendix~\ref{ch:zipping-problems} considers both problems in turn, offering potential fusion strategies for each. While these may be legitimate cases to consider in a general purpose fusion framework, they do not appear in the vectorised \name{Data Parallel Haskell} code. Since \DPH is currently the primary target for the application of \LiveFusion, the fusion of these cases is left as future work.
\clearpage
\section{Random access combinators}
\label{sec:Loops-random-access}
The combinators discussed so far consumed their inputs in a sequential manner from beginning to end. However, there are cases (in \DPH inclusively) where elements need to be picked from the array at random. In particular, the @backpermute@ combinator (@bpermute@ for short) creates a new array by picking elements at given indices:
\begin{hscode}
bpermute :: Array a -> Array Int -> Array a
bpermute [0,10,20,30,40,50] [3,4,5,1]
> [30,40,50,10]
\end{hscode}
To understand the translation of random access combinators to \Loop language representation we must first recall how sequential looping is done. Whenever a sequential rate\irate $r$ is established, the looping statements are inserted into the loop (Figure~\ref{fig:sequential-looping}). The corresponding index variable @ix@\sub{r} is initialised (line 3) and updated (line 15) and the looping range is established (line 7).
\begin{figure}
\begin{loopcode}[%
numbers=left,
literate=
{_xs}{{\sub{xs}}}2
{_r}{{\sub{r}}}1
]
init_xs/_r:
let len_xs = arrayLength arr_xs
let ix_r = 0
goto guard_r
guard_xs/_r:
unless ix_r < len_xs | done_r
goto body_r
body_xs/_r:
let elt_xs = readArray arr_xs ix_r
goto yield_r
yield_xs/_r:
ix_r := ix_r + 1
goto bottom_r
\end{loopcode}
\caption{Sequential indexing in the \Loop language.}
\label{fig:sequential-looping}
\end{figure}
However, the statement reading the @xs@ array is oblivious to how the index variable was computed. It will use any value @ix@\sub{r} currently has. In order to read variables at random, the @xs@ array the rate $r$ is no longer considered to be sequential and no index initialisation/update statements are inserted. Instead, the @backpermute@ combinator will set the @ix@\sub{r} variable to the appropriate value to read @xs@ at the required index.
The code presented in Figure~\ref{fig:Loop-bpermute} has been simplified to only include the statements relevant to reading @xs@ array at the index read from @is@ array. The complete code is presented in Appendix~\ref{fig:Loop-bpermute-complete}.
\begin{bluebox}
Note that the array read on line 4 has been generated by the combinator responsible for @xs@ array and is oblivious to the fact that @xs@ would be read at random. Technically, @xs@ does not need to be a manifest array! Any pipeline of combinators that can produce an element given an index will suffice. As such, the following expression will also fuse:
\begin{hscode}
bpermute (map (+1) [0,10,20,30,40,50]) [3,4,5,1]
> [31,41,51,11]
\end{hscode}
\end{bluebox}
\begin{figure}
\begin{loopcode}[%
numbers=left,
literate=
{_xs}{{\sub{xs}}}2
{_r}{{\sub{r}}}1
{_is}{{\sub{is}}}2
{_bperm}{{\sub{bperm}}}5
]
body_bperm/_is:
let elt_is = ... -- produce index
let ix_r = elt_is -- set index to read xs at
let elt_xs = readArray arr_xs ix_r -- read xs array
let elt_bperm = elt_xs -- set result element
\end{loopcode}
\caption{\Loop code for reading \code{xs} array at index \code{ix}\sub{r} set by \code{backpermute} combinator. where both data (\code{xs}) and indices (\code{is}) arrays are manifest and the result array is forced. Complete code is given in Appendix~\protect\ref{fig:Loop-bpermute-complete}.}
\label{fig:Loop-bpermute}
\end{figure}
The \*rate system* of the \Loop language makes it straightforward to switch between sequential and random accessing. Statements responsible for sequential looping (index initialisation and updates) are not inserted into the loop until the very end. This makes it possible for individual combinators to override that behaviour and take on the responsibility of setting the appropriate indices.
%\clearpage
%\section{Array generators: Enumeration and Replication}
\clearpage
\section{Segmented array combinators}
\label{sec:Loops-segmented-combinators}
\isegcomb
The process of vectorisation in \name{Data Parallel Haskell} and in particular its \name{Flattening transform} (Section~\ref{sec:Flattening}) mandates the need for combinators that operate on segmented arrays in the backend library. They have been discussed in an earlier chapter in Section~\ref{sec:DPH-segmented-combinators}.
Segmented arrays is a representation of nested arrays where all of the data is stored in a single flat array and a separate segment descriptor defines the partitioning of the data array into subarrays, called segments.
It was said that segmented combinators fall into two categories:
\begin{enumerate}
\halfspacing
\label{segmented-classification}
\item Combinators that \*produce* elements at the \*rate* of the segment descriptor, i.e. one element per segment (Figure~\ref{fig:fold-s}).
\item Combinators that \*produce* elements at the \*rate* of data, i.e. producing entire segments (Figure~\ref{fig:scanl-s}).
\end{enumerate}
The discussion of the combinators proceeds with reference to the two combinator categories.
\subsection{Nested loops}
Conceptually segmented combinators resemble nested loops in procedural languages where for each element taken from the segment descriptor array, that many elements of the data array get processed.
So far in this chapter we have been looking at flat loops. In the \Loop language they have the standard structure and control flow presented in Figure~\ref{fig:CFG-flat-segmented} (left).
\begin{bluebox}
In order to support nested loops the \Loop language offers a special basic block -- \[nest].
If a loop contains a nested loop, the \[nest] basic block transfers control to it. After the nested loop is finished, the control is returned to the \[body] block of the outer loop.
\end{bluebox}
The default control flow for all nested combinators is shown on Figure~\ref{fig:CFG-flat-segmented} (right).
\begin{figure}
\begin{subfigure}{.4\textwidth}
\includegraphics[center,scale=\omniscale]{img/CFG-basic}
\end{subfigure}%
%
\begin{subfigure}{.6\textwidth}
\includegraphics[scale=\omniscale]{img/CFG-Segmented}
\end{subfigure}
\caption{Default control flow between basic blocks in flat loops (left) and nested loops (right).}
\label{fig:CFG-flat-segmented}
\end{figure}
The following sections introduce the translations of the most prominent segmented combinators to the \Loop language.
\subsection{Segmented reductions}
\label{sec:Loops-segmented-reductions}
Segmented reductions represent the first type of segmented combinators outlined on page~\pageref{segmented-classification}. They reduce each data segment to a single scalar value.
An example of @fold_s@ application is shown in Figure~\ref{fig:fold-s}.
\begin{figure}
\includegraphics[scale=\omniscale]{img/Example-fold-s}
\caption{Segmented fold.}
\label{fig:fold-s}
\end{figure}
Recalling the \Loop language conventions, a single element @elt@\sub{fold} should be produced for every iteration of the \*outer* loop. Incorporating the new \[nest] block into the loop, the call to a @fold_s@ results in the \Loop in Figure~\ref{fig:Loop-fold-s}.
The code presented here has been simplified to only include statements generated by the call to @fold_s@. In particular the details of @elt@\sub{segd} and @elt@\sub{data} have been omitted. The complete code is presented in Appendix~\ref{fig:Loop-fold-s-complete}.
Notably, @fold_s@ can fuse with both the \*segment descriptor* and the \*data* loops. Additionally, it will fuse into its consumer. In fact, to any combinator consuming the output of @fold_s@ it will be indistinguishable from a flat combinator.
\begin{figure}
\begin{subfigure}{.50\textwidth}
\begin{loopcode}[%
literate=
{_1}{{\sub{fold}}}3
{_3}{{\sub{segd}}}3
{_4}{{\sub{data}}}3,
]
init_1/_3/_4:
...
let z_1 = 0
goto guard_1
%\CommentPlusPlus{Outer loop}%
guard_1/_3:
...
goto nest_1
nest_1/_3:
let elt_3 = ...
-- reset accumulator
let acc_1 = z_1
-- find segment boundary
let end_3 = ix_4 + elt_3
-- enter inner loop
goto guard_4
body_1/_3:
-- the fold value
let elt_1 = acc_1
goto yield_1
yield_1/_3:
...
goto bottom_1
bottom_1/_3:
goto guard_1
done_1/_3/_4:
...
\end{loopcode}
\end{subfigure}%
%
\begin{subfigure}{.50\textwidth}
\begin{loopcode}[%
literate=
{_1}{{\sub{fold}}}3
{_3}{{\sub{segd}}}3
{_4}{{\sub{data}}}3,
]
%\CommentPlusPlus{Inner loop}%
guard_4:
-- exit inner loop at the end of segment
unless ix_4 < end_3 | body_1
goto nest_4
nest_4:
goto body_4
body_4:
let elt_4 = ...
goto yield_4
yield_4:
...
goto bottom_4
bottom_4:
-- update accumulator
acc_1 := acc_1 + elt_4
goto guard_4
% %
\end{loopcode}
\end{subfigure}
\caption{\Loop code for \code{folds (+) 0 segd data}. Complete code is given in Appendix~\protect\ref{fig:Loop-fold-s-complete}.}
\label{fig:Loop-fold-s}
\end{figure}
Other combinators that run at the rate of the segment descriptor include @count_s@, @sum_s@ and several others. However, they are all implemented in terms of @fold_s@:
\begin{hscode}
-- Count the number of occurences of a value in each segment
count_s :: Term a -> Array Int -> Array a -> Array Int
count_s x segd = fold_s (+) 0 segd
. map boolToInt
. map (==. x)
where boolToInt b = if b ==. true
then 1
else 0
sum_s :: Num a => Array Int -> Array a -> Array a
sum_s = fold_s (+) 0
\end{hscode}
\subsection{Segmented data-rate combinators}
\label{sec:Loop-segmented-data-rate-combinators}
In the previous section we have covered segmented reductions that produce arrays of the size of the segment descriptor. A different type of segmented operations are those that produce a data array containing segments of specified lengths.
An example of @scan_s@ application is shown in Figure~\ref{fig:scanl-s}.
\begin{figure}
\includegraphics[scale=\omniscale]{img/Example-scanl-s}
\caption{Segmented left scan.}
\label{fig:scanl-s}
\end{figure}
Following the \Loop language conventions every iteration of the \*inner* loop must produce an element @elt@\sub{scan} of the result array. The relevant part of the \Loop code are shown in Figure~\ref{fig:Loop-scanl-s}.
As before, the code presented has been simplified to only include statements generated by the call to @scan_s@. The complete code is available in Appendix~\ref{fig:Loop-scanl-s-complete}.
As in the case with @fold_s@ and all other segmented combinators, @scanl_s@ can fuse with both the \*segment descriptor* and the \*data* loops as well as its consumer.
\begin{figure}
\begin{subfigure}{.5\textwidth}
\begin{loopcode}[%
literate=
{_1}{{\sub{scan}}}3
{_3}{{\sub{segd}}}3
{_4}{{\sub{data}}}3,
]
init_1/_3/_4:
...
let z_1 = 0
goto guard_3
%\CommentPlusPlus{Outer loop}%
guard_3:
...
goto nest_3
nest_3:
let elt_3 = ...
-- reset accumulator
let acc_1 = z_1
-- find segment boundary
let end_3 = ix_4 + elt_3
-- enter inner loop
goto guard_1
body_3: