Tiled Array Design Decision Document

Updated: Monday March 31, 2008

Email issues and comments to Brad and he will integrate them into this document.

How to read this Parnas-light design document.

A Tile is a subset of an array obtained by dicing it evenly into n-dimensional rectangles. A tile is associated with the array from which it was derived and has the same number of dimensions. Each dimension can be a different size. Optionally extended overlapping regions can be included as well. Tile elements are defined the same way as for arrays.

An Area is a n-dimensional rectangular subset of an array. It is used to denote an area of interest to be processed. The region outside the Area is excluded. Either an area can be Tiled or an entire array.

The goal is to integrate Tiles into ASAP as a first class object. That is, boxes can be written to process streams containing Tiles in a consistent fashion.

• How are Tile dimensions encoded?

1  Encode as a length in bytes
   0 They may not all be the same length in edge cases.

2  Encode as a length in elements.
   0 They may not all be the same length in edge cases.
   + Tile operations use length in elements.
   + If denoted, the length would be in elements.

3  Encode as the number of partitions.
   ? For at least the dice case, the number of partitions is more useful. 

Status: The ChunkIt iterator is using a length in elements.

• How are Tile dimensions denoted?

1  Denote as a length in elements
   0 They may not all be the same length in edge cases.

2  Denote as the number of partitions.
   ? For at least the dice case, the number of partitions is more useful.

3  Tile dimensions are not denoted in XML.

Status:  (3) until a need arizes.

• How is the Tile location in the array encoded?

1  Encode as a set of coordinates.
   - The requires storing a vector of coordinates.

2  Encode as an integer Tile sequence.  See folded index below.
   + Uses only an integer.  Easy to store and copy.

3  Encode as the offset to the first element in the associated array.
   - Depends on a particular array encoding.

   + Jen prefers to encode locations as offsets from index 0.  

   + This can be extended to sparse arrays by flattening the array and
     pointing to where they would be in offset space.

4  Store a Tiling schema in the catalog.
   - The engine requires RPC calls to modify the catalog.

5  Store Tiling schema in a Tile header.
   - The schema is repeated in each Tile.

Status: The ChunkIt iterator has a method to convert a Tile sequence number to an element offset to the first element. The iterator starts from the element offset to the first element.

• How is the Tile location in the array denoted?

1  Automatic; Tiles are not specified in XML.

2  Automatic or define Tiling using box parameters.
   + Flexible; allows either mode.
   + Useful for experiments; even if not used in the final version.
   + Tiling can be localized to custom experimental boxes.

3  Denote as a set of coordinates in XML.
   - Tiling would be visible to users.

4  Denote as an integer Tile sequence.
   + More compact than coordinates.

• How can streams of Tiles be connected?

At a minimum streams of Tiles need to be passed between boxes on the same node. This requires that connected boxes have access to the Tile definition.

1  Intermediate streams between boxes on different nodes.
   + This is needed for Nathan's work.

2  Input and Output to Clients
   - Tiling is done for performance and should be transparent to the user.
   - This would require an XML representation for Tiles.

• How do Tiles propagate through streams?

1  A fixed number of elements in each dimension.

2  A different overlap size for each dimension.
   - This is not commonly done in applications.
   - It would increase complexity, space, and performance overhead.

3  Use a sequence number (so we know their parent/associated array)
   and where they are in the larger array.

4  A Tiled array is a different encoding of an array and is not visible
   outside the array.

Status: Up to now Jen has used option 4.

• What do we call a regular chunk?

1  Regular Chunk

2  Chunk
   +  Only irregular chunks are referred to by specialized names.

3  Tile
   +  It implies that it is part of the larger, regular set that fits together.
   +  It allows it to be differentiated from arbitrary chunks.

4  Dice
   + Rhymes with slice.

Status:  The final choice is Tile.

• What do we call the associated array schema?

1  Originating Schema

2  Parent Schema
   - Terminology is more appropriate for multi-level hierarchies.

   + Connoting membership to a larger set.

   + With some partitioning schemes (like recursive Tiles) we may
     incidentally create a hierarchy.

3  Super schema
   - Terminology is more appropriate for multi-level hierarchies.

   + Connoting membership to a larger set.

   + With some partitioning schemes (like recursive Tiles) we may
     incidentally create a hierarchy.

4  Primary Scema

5  Principal Scema

6  Source Schema

• How are sparse integer dimensions partitioned?

Sparse dimensions are specified over a 32 bit signed integer range. An instance of a sparse dimension will range over a minimum and maximum.

1  Over the whole 32 bit range.
2  Over the used range.
3  Over a specified range that includes the used range.
4  Over a specified range that excludes outlyers.

• How are string dimensions partitioned?

1  Do not partition; include the entire dimension.
2  Do not allow arrays with any string dimensions to be partitioned.
3  Partition based on the number of strings defined for the dimenstion.

• How is the overlap specified?

1  A fixed number of elements in each dimension.

2  A different overlap size for each dimension.
   - This is not commonly done in applications.
   - It would increase complexity, space, and performance overhead.

• How is the overlap refreshed?

Each time an array with overlap is transformed the overlap becomes stale. It needs to be refreshed by copying updated elements from its neighbors.


1  Allow only one operation that modifies overlaps and then merge Tiles.
2  Provide interconnect channels for refreshing overlaps.

N Dimensional Array Computations

Definitions

n    Number of dimensions; Dimensions range from 1 to n.
Si   Width of an array dimension:  <Upper Bound> - <Lower Bound> + 1
Ci   Width of a Tile dimension.
Ii   Zero-based index into a dimension:  <Actual Index> - <Lower Bound>
I    Folded index:  I1 + S1 * (I2 + S2 * (I3 + ... + Sn-1 * In))
                    I1 + S1 * I2 + S1 * S2 * I3 + ... + S1 * ... * Sn-1 * In-1))

• The offset into a dense array is:

I * sizeof( <Element> )

• Indecies can be extracted from a folded index:

:  From low to high dimensions:
:
I1   = I  mod S1      Q1   = I  / S1
Ii+1 = Qi mod Si+1    Qi+1 = Qi / Si+1


:  From high to low dimensions:
:
In   = I  / (S1 * ... * Sn)        Rn   = I  mod (S1 * ... * Sn)
Ii-1 = Ri / (S1 * ... * Si-2)      Ri-1 = Ri mod (S1 * ... * Si-2)
I1   = R2

• A Tile can be accessed in a dense array:

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:  This version assumes there are no short edges and excludes overlaps.
:.....................................................................


DO i = 1  TO  1 * C2 * .. * Cn
   DO C1 TIMES
      : Access each element in a contiguous line.
      : Increment the address by the element width.
   END DO

   : We can exit the loop here on the last iteration.
   :
   q    = i
   jump = S1 - C1

   DO j = 2  TO  n
   UNDO IF q mod Cj
      q = q / Cj

      jump += Sj-1 * (Sj - Cj)
   END DO

   : Increment the address by the jump times the element width.
END DO



::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:  This version accomodates short edges, but excludes overlaps.
:.....................................................................


:  Shorten the linear scan if short in the lowest dimension.
:
cl = S1 mod C1

IF cl = 0  OR  e mod S1 <> S1 - cl:   IF
   cl = C1
END IF


:  Reduce the total iterations if short in the highest dimension.
:
ch = Sn mod Cn

IF n = 1  OR  Ch = 0
   ch = Cn

ELSE
   p = Sn - ch

   DO j = 1  TO  n - 1
      p *= Sj - Cj

      IF e < p
         ch = Cn
   UNDO
      END IF
   END DO
END IF

DO j = 2  TO  n - 1
   ch *= Cj
END DO

skip = 0

DO i = 1  TO  ch
   IF skip
      skip -= 1
      : Increment the address by C1 times the element size.

   ELSE
      : This loop can be performed as a vector operation.
      :
      DO cl TIMES
         : Access each element in a contiguous line.
         : Increment the address by the element width.
      END DO

      : Increment the address by (C1 - cl) times the element width.
   END IF

   IF skip = 0
      q    = I
      jump = S1 - C1
      p    = S1

      DO j = 2  TO  n - 1
         :  Skip if short in any interior dimension.
         :
         sm = Sj mod Cj
         qm = q  mod Cj

         IF sm  AND  qm => sm  AND  (I mod p) * Sj => p * (Sj - sm)
            skip = Cj - sm
         END IF

      UNDO IF qm
         p *= Sj
         q  = q / Cj

         jump += Sj-1 * (Sj - Cj)
         skip = 0
      END DO
   END IF

   : Increment the address by the jump times the element width.
END DO

Developer Links