# 3D Tiled Code Generation for [PERSON]'s Algorithm
## 3 Materials and Methods, 3D Tiled Code Generation  
To implement the calculations represented with Listing 1, we use a calculation model based on a network of computational cells suggested by Figure 1 for \(n=7\), that is, a triangle of cells. Each cell runs instances of statement S1 and statement S2. Cells use shared memory for reading and writing results produced with them. So, results calculated by cells are held in shared memory. At a particular time unit, cell \((i,j)\) updates the value of \(S(i,j)\) running an instance of statement S1 when the values produced with instances of S1 by means of cells \((i,k)\) and \((k+1,j)\), which we call the horizontal and vertical mates of cell \((i,j)\), respectively, are ready (already updated). In Figure 1, the mates of cells 01, 02, 03, and 06 are connected with those cells with the arrows in the same color. The rest of the arrows connecting a cell with its mates are skipped in order to not clutter the drawing. Taking into account that before calculation, i.e., in time unit 0, for a given \(i,i=1,2,\ldots,n-1\), \(S(i,i)=0\) and supposing that each cell requires one time unit to complete the execution of an instance of statement S1, from Figure 1, we conclude that for a cell \((i,j)\) and a given \(k\), the time unit of completing the calculation of a horizontal mate is the following \(t1=k-i\), whereas the time unit of completing the calculation of a vertical mate is as follows: \(t2=j-k-1\). For example, for cell 01 its mates 00 and 11 are ready at time 0 because for cell 01, \(k=0\). As far as statement S2 is concerned, it is to be executed at the time unit when the value of \(S(i,j)\) produced with statement S1 by means of loop \(k\) has already been completed (completing the execution of loop \(k\) for given values of \(i\) and \(j\)). From Figure 1, it is clear that for cell \((i,j)\), the time unit of completing the calculation of S1 with loop \(k\) is equal to \(j-i\), for example, for cell 01 that time unit is 1, for cell 02 that time unit is 2, and so on. To guarantee that statement S2 is executed at the time unit when loop \(k\) completes the calculation of S1, but after statement S1, we introduce the second time unit dimension whose value is 0 for statement S1 and 1 for statement S2, i.e., the time of completing S1 for cell 01 is (1,0), whereas the time of completing S2 for cell 01 is (1,1). Table 1 presents time units \(t1\), \(t2\) of completing the calculations of \(S1(i,k)\) with statement S1 (a horizontal mate) and \(S1(k+1,j)\) (a vertical mate) with statement S1 as well as  
Figure 1: Calculation model to update cells. the time units of completing the execution of statements S1 and S2 for cells 01 to 06. The time of the execution of statement \(S1\) for given \(i,j\) and \(k\) is calculated as \(max(t1,t2)+1\), where \(t1\) and \(t2\) state for the completing time of the horizontal and vertical mates, respectively, i.e., next time after all the operands of statement \(S1\) are ready. It is worth noting that statement \(S2\) is executed only when all the iterations of loop \(k\) are already finished. It is worth mentioning that at the same time unit, a cell can combine two or more pairs of values produced with mates for statement S1. For example, at time unit (2,0), cell 02 updates two times; at that time unit, it combines values generated with mates 00 and 12 as well as 01 and 22 because at time unit (2,0) all those mates complete their updating. In such a case, output dependences arise, which we will respect due to serial updates performed with the corresponding cell as described below in this section. Table 2 presents the time units of the completion of all cells shown in Figure 1--the time units of the completion of statement S2. To generate code, we form the following set \(CODE\) whose constraints take into account the consideration mentioned above. \[