Views and Slices

This document introduces two constructs Seashell provides for hardware safe parallel access. The first construct is a Slice which allows the programmer to statically slice an array in several parts, each of which can be accessed in parallel. The second construct is a View which is the only way of accessing several elements of a Seashell array. The two constructs together provide the ability to perform a variety of array computations in a safe manner.

Rationale

One of the most important benefits of reconfigurable hardware is the ability to access multiple pieces of the memory at the same time. However proving that an arbitrary array access is hardware safe (i.e. accesses distinct hardware banks) at compile time can quickly become intractable.

To combat this problem, seashell provides Views which can we thought of windows that walk over the array and can access elements in the array in parallel. Having Views reduces the proof burden on the Seashell type system because instead of having to figure out what elements are being access in each iteration, the user specifies them exactly which allows the type system to be simpler.

However, just having Views is not enough (This is an unverified claim - Rachit). Sometimes, it the programmer might want to access different slices of the array at the same time. If we allow unrestricted usage of views for this i.e., allow one array to have multiple views into it, we again face the problem of establishing mututal exlcusion between all the views in the array which may an undecidable problem.

Instead of allowing for unrestricted views, Seashell instead asks the programmer to slice an array into mutually exclusive parts that the user wants to access in parallel. Since slices are always mututally exclusive, the burder of proof on the type system is again reduced.

While a combination of views and slices is still a conservative approximation of the the set of all safe parallel accesses, we hope that together they are expressive enough to allow for common array programming patterns.

Slices in Seashell

A Slice in seashell is a way of logically separating an array into separate pieces that can be traversed in parallel. A Slice only exists at the Seashell language level and is compiled away to normal array and bank accesses by the compiler.

For example, consider the following array \(a\) of length 8 and banking factor 2. By default, we assume interleaving banking for elements, which means alternative elements exist in separate banks.

Next, we define a static slice of \(a\) using the following syntax:

let (b, c) = slice[w=4] a

The slice w=w arr syntax gives us access to two mutually exclusive parts from a starting array arr. The w defines the length of the window that separates the array. The slice operator uses the banking structure of the array arr to infer the banking structures of the resulting arrays. In this case, Seashell will infer that b and c are both int[4 bank (2)] arrays. Furthermore, since b and c are themselves just arrays, we can further slice them into smaller arrays still.

The current syntax, however, does not allow us to create slices of the following form:

In order to allow programmers to slice arrays in this form, we extend the slice syntax as follows:

let (b, c) = slice[w=4, s=2] a

This syntax allows us to specify a stride length that describes how many elements get skipped over when constructing the slices. In this case, the typechecker will infer from original structure of a that both b and c are int[4 bank (1)].

Furthermore, this syntax can also easily infer when a given slicing is invalid:

let (b, c) = slice[w=3, s=3] a

Since this array doesn’t have a simple banking structure that can be inferred from the original array a, Seashell will fail to typecheck it.

Finally, this syntax can naturally be extended to multiple dimensions:

int[4 bank(2)][4 bank(2)] a;
let (b, c) = slice[w=4, s=2][w=2] a;

where, b and c are int[2][4 bank(2)].

Views in Seashell

While slices provide a way to divide arrays into mutally exclusive sdifferent egments, we still need a way of accessing the elements of a slice in a safe and parallel manner. Views provide a mechanism to do exactly this. Instead of asking for a mutually exclusive slice, a view asks Seashell if a given set of accesses are hardware-safe i.e., they all correspond to distinct banks. Notice that this constraint is different from slices since Seashell doesn’t require a slice to only consist elements stored in different banks.

The view syntax is very similar to the slice syntax:

let v_a = view[w=2, s=1, o=0] a

which results in a view as follows:

In a similar fashion to the slice syntax, w dictates the width of the view, s is the stride used to generate the view, and o is the offset at which the view starts.

When we define an offset with a view, we have the following picture:

However, as previously mentioned, a view needs to ensure that all elements accessed in it are in distinct banks. Since this is not the case with this view, Seashell will reject it.

Views in loops

Since parallel memory access are primarirly used in conjunction with loops, we can use views with dynamic offsets:

for (let i = 1..10) {
    let v_a = view[w=2, s=1, o=i] a;
    let v_c = view[w=2, s=1, o=i] c;
    v_c := v_a;
}

Assignment b/w views corresponds to the intuitive parallel writes between two pieces of memory. To make sure that the expression v_c := v_a is safe, all Seashell need to do is make sure v_c and v_a have the same widths.

Desugaring loop unrolls to views

This is intentionally blank…