subject ：TENET: A Framework for Modeling Tensor Dataflow Based on Relation-centric Notation
Time ：2021
meeting ：ISCA
Research Institute ： Peking University

TENET

summary

There is an iteration domain $D_S$, Access function $A_{S,F}$, as well as PE Interconnection. We define an affine transformation , use $m\times n$ The matrix represents , This matrix is what we will optimize dataflow, namely S and spacetime-stamp Of relation. thus , You can get a series of relationship sets ：data assignment relation（ The relationship between timestamp and tensor , come from dataflow）、spacetime-stamp map relation（ It will be used as a constraint in performance calculation , from PE interconnection obtain ）. thus , Calculate the performance based on these sets . There are constraints in the calculation of relation sets , That is, the constraints of the optimization problem . Using the method of integer programming , Calculate the optimal solution .

I. Introduction

A typical spatial architecture consists of processing elements (PE) Array and register . The main feature of spatial architecture is a variety of hardware data flow choices .
hardware dataflow It describes ：1） Loop instances to PE array Distribution and 2）PE Execution sequence of loop instances in .
Summary of some existing work ： Hardware data flow is crucial to achieve high throughput and low latency , Because it decides PE utilization 、 Data access mode and on-chip bandwidth requirements . Different tensor calculations prefer different hardware data streams . for example , Google's tensor processing unit (TPU) [22] Connect with pulsating data flow PE, Each of them PE Responsible for a multiplication and addition operation . and Camircon [31] Connect through multicast communication network PE, Each of them PE Execute a dot product . Other spatial structures , Such as DySER [19] and Plasticine [42], Integrate in a flexible way PE And its interconnection , Therefore, it can support a wider range of applications .
Now? ,a formal notation is still strongly desired to represent hardware dataflow. A mark (notation) It should be able to systematically cover the entire data flow design space , And promote simple and accurate performance modeling . There are two kinds ：compute-centric The measurement of cannot measure data transmission 、 reusing ;data-centric Measured MAESTRO The model is defective .
This article defines TENET, The core part is relation-centric notation. We define the following relationship ：1） Loop instances and execute calculations PE The relationship between ,2） Loop instance and its in PE Order of execution in ,3）PE And the corresponding assigned tensor elements , as well as 4）PE Connect to the interconnection network . Overall speaking ,TENET Be able to estimate various hardware indicators , Including data reuse 、 Delay 、PE Communication bandwidth and on-chip memory bandwidth .

II. Background

A. Spatial Architectures

The PE also contains register files for data storage.
Usually , The spatial architecture has a three-tier memory hierarchy , namely PE Register level 、 On chip registers and off chip memories . For the sake of simplicity , We make the following two assumptions when modeling the hardware behavior . First ,ALU Be able to perform a multiplication and addition (MAC) operation . secondly , By adjacency PE Data transmission between interconnections takes a cycle .
When designing data flow , Data reuse It is the key factor to achieve high performance and low energy consumption , It can be further divided into time reuse and space reuse . Time reuse occurs when the same data is reused in different cycles , Spatial reuse occurs when the same data is different PE When reusing .

B. Notation Basics

In this paper, TENET supports tensor applications with perfectly-nest loops and single unconditional statement.

What is a perfectly nested loop?
A perfectly nested loop is a nested loop, where all the assignment instructions are inside the innermost loop.

Iteration domain： Iteration domain . for example ,$D_S=\{S[i,j]:0\le i<4,0\le j<3\}$.
Access function：Given a loop instance, the access function returns the tensor elements accessed by the statement S. We use a relation to represent the access function of tensor F. $$A_{S,F}=\{S[\vec{n}]\to F[\vec{f}]\}$$
for example , In the figure 1 Of 1D-CONV In operator , tensor Y The access function of is $\{S[i,j]\to Y[i]:0\le i<4,0\le j<3\}$, Represents a loop instance S[i, j] Access tensor elements Y[i].

C. Limitations of Existing Dataflow Notations

III. TENET Overview

IV. Relationship centered notation

TENET Four relationships are defined , Including loop instances to PE Array mapping （Section IV-A）、 Data distribution （Section IV-B）、PE interconnection （Section IV-C）、 Mapping between different spatiotemporal markers （Section IV- D). Use relationship centric symbols , We can accurately determine the execution position and time of each cycle instance in the spatial architecture , Access the location and time of tensor elements , And how tensor elements span PE Move .

A. Dataflow Relation

Definition 1：Dataflow：Given a statement S with iteration domain D_S and iteration vector $\vec{n}$, the dataflow is defined as
$${\Theta }_{S,D}=\{S[\vec{n}]\to (PE[\vec{p}]|T[\vec{t}])\},S[\vec{n}]\in D_S$$
It will loop the instance S[n] Assign to a timestamp , It is a pair of space stamps PE[p] And time stamp T[t].Θ The footmark of D It should refer to the collection of space-time stamps , instead of S Iteration domain of D_S. This is later IV-D Part can also reflect .

Upper figure ,${\Theta }_{S,D}=\{S[i,j,k]\to (PE[i,j]|T[i+j+k])\}$. generally speaking ,$\Theta$ Is equivalent to loop iterator S By affine transformation to timestamp .
Dataflow Design space ：n Is the number of layers of the cycle ,$n\times n$ Is the size of the affine transformation matrix , Each element of the matrix is 0 or 1, So it is 2 The index of , The design space size is $O(2^{n^2})$. I think we should use $m\times n$ Matrix times $n\times 1$ Vector (S Index vector of ), The result is $m\times 1$ Vector ,m Is the total dimension of time stamp . For example, above m=3,PE There are two dimensions ,T There is one dimension .

B. Data Assignment Relation

Definition 2：Data assignment： Given Dataflow ${\Theta }_{S,D}$, Definition data assignment by ：

A The footmark of D It's a collection of time stamps . In an effort to 3 For example , tensor Y Of data assignment yes ：

For this example , We observe each of PE Always calculate the same output tensor at different timestamps (Y), This means tensor Y[i, j] Keep still , And reuse iteratively with different timestamps , Until the calculation is complete .

C. Interconnection Relation

Definition 3：PE Interconnection： Given a PE array,interconnection It's a collection , Each of these elements is described from a PE To another PE Mapping .
c1, … , ck Is used to describe PE Topological conditions .PE Only through other PE Or register (scratchpad) get data . this paper , We modeled 3 Common PE Interconnection topology ：

D. Spacetime-stamp Map Relation

Definition 4：Spacetime-map： Given a data stream ,spacetime-map Is a relational set , It will stamp a set of time and space D Map to another set of spatiotemporal markers D’. D and D’ From a given data stream .

We can assume that the time distance of D and D’ is within 1, and the PE specified by D and D’ are interconnected. So as to write some map, In an effort to 3 For example ：

combination data assignment, Yes ：

The illustration above Y[0,0] The reuse situation of .

The illustration above A[0,0]、B[0,0] The reuse situation of .
Practical application , We can ：1） Limit D and D’ Contains the same PE, Time reuse of data can be captured （temporal reuse）;2） Limit D and D’ Include connected PE, Can capture spatial reuse of data （spatial reuse）.

V. Performance Model

A. Data reuse and Volume Model

surface 2 Medium sum Indicates the number of elements in the calculation set . Are for a particular tensor F In terms of the .
TotalVolume： Every time the data used is calculated . for example ,the TotalVolume of tensor A in Figure 3 can be calculated as

ReuseVolume： Reuse data .
UniqueVolume： New data at each point in time , Get from the register .
ReuseFactor Describes the average number of times to reuse data obtained from the register memory .
SpatialReuseVolume: The SpatialReuseVolume sums up the volume of data with spatial reuse at different space-stamps, where D and D’ contain interconnected PEs only.
TemporalReuseVolume: only refers to the temporal reuse at the same PE, where D and D’ contain the same PE.
therefore , Yes ReuseVolume = SpatialReuseVolume + TemporalReuseVolume.

B. Latency and Bandwidth Model

The delay of data flow includes each PE Communication delay and calculation delay in . We assume that buffers、networkds And arithmetic units work in a pipeline , And use double buffering Wait for technology to hide latency . that , The overall delay is only the maximum value of communication delay and calculation delay .
PE Array and scratchpad Communication delay ：

Calculation delay ：

among $D_S$ Is the iteration domain ,sum Is the total number of iteration fields ,$Uti{l}_{PE}$ yes PE The average utilization rate of .
IBW(interconnection bandwidth)：

SBW(scratchpad bandwidth)：

C. Model implementation

Used C++ Of ISL Kuhe Barvinok library .

VI. Evaluation

benchmark: GEMM, 2D-CONV, Matrix multiplication chain (MMc), Matricized tensor times Khatri-Rao product (MTTKRP), Jacobi-2D