Skip to main content

2 GenDP

1 Motivation​

ASICs tend to have significantly different architectures for different kernels to extract the best performance. However, the divergence of ASIC designs makes it difficult to run commonly used modern sequencing analysis pipelines due to software integration and programming challenges. Generic

In the commonly used genome sequencing pipelines, dynamic programming (DP) algorithms are widely used. DP algorithms are adopted by many genomics kernels and account for large amounts of time in mainstream sequencing pipelines. Generic DP acceleration

With the observation that many genomics kernels are dominated by dynamic programming (DP) algorithms, Fuse various kernels:

  • DPAx: a DP accelerator (dynamic programming acceleration)
  • DPMap: a graph partitioning algorithm (maps DP objective functions to the accelerator)

DP kernels with various dependency patterns, such as 1D and 2D DP tables and long-range dependencies in the graph structure.

2 Challenges​

Challenge: accelerating a general-purpose DP algorithm 1). DP kernels in common sequencing pipelines have different dependency patterns, including both 1-Dimension and 2-Dimension DP tables. Some kernels have long-range dependencies in the graph structure. 2). DP kernels have different objective functions which include multiple operators. Different alignment mode and various scoring method: linear, affine, and convex. 3). DP kernels have different precision requirements.

  • high efficiency for low-precision computation
  • high accuracy for high-precision computation

3 Proposal​

  • DPAx: a DP accelerator
    • solve multiple dependency patterns
      • flexible PE interconnections.
  • DPMap: a graph partitioning algorithm
    • support different objective function
    • support multiple precision arithmetic
      • programmable compute units
      • specialized dataflow

4 DP kernel choices​

  • Banded Smith-Waterman (BSW)
  • Chain
  • Pairwise Hidden Markov Model (PairHMM)
  • Partial Order Alignment (POA)

extending to non-sequence-alignment algorithms

  • Dynamic Time Warping (DTW) which is commonly used for speech detection
  • Bellman-Ford (BF) algorithm for shortest path search in robotic motion planning tasks

5 DP​

Quanlification: DP table (element: the length of the Longest Common Subsequence between X(0,i)X(0,i) and Y(0,j)Y(0,j).

c[i,j]={0if i=0 or j=0c[i−1,j−1]+1if i,j>0 and xi−1=yj−1max⁡(c[i,j−1],c[i−1,j])if i,j>0 and xi−1≠yj−1(1)c[i,j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ c[i-1,j-1] + 1 & \text{if } i,j > 0 \text{ and } x_{i-1} = y_{j-1} \\ \max(c[i,j-1], c[i-1,j]) & \text{if } i,j > 0 \text{ and } x_{i-1} ≠ y_{j-1} \end{cases} \tag{1} X(0,i)∈[[x0],[x0,x1],[x0,x1,x2],...,[x0,x1,x2,...,xm]]X(0,i) \in [[x_{0}], [x_{0}, x_{1}], [x_{0}, x_{1}, x_{2}], ..., [x_{0}, x_{1}, x_{2}, ..., x_{m}]] Y(0,j)∈[[y0],[y0,y1],[y0,y1,y2],...,[y0,y1,y2,...,yn]]Y(0,j) \in [[y_{0}], [y_{0}, y_{1}], [y_{0}, y_{1}, y_{2}], ..., [y_{0}, y_{1}, y_{2}, ..., y_{n}]]

Interactive DP Table

6 Genomics Pipelines & corresponding DP Kernels​

  • read alignment, RNA & protein alignment: BSW
  • post-alignment variant calling: PairHMM
  • polishing step of assmbly: POA
  • both alignment and assembly of long read sequencing: Chain

1) BSW​

  • estimates the pairwise similarity between the query and reference sequences
    • similarity score: affine-gap penalties

Objective function:

  • Match:
H(i,j)=max⁡{H(i−1,j−1)+S(X(i),Y(j)),E(i,j),F(i,j)}H(i,j) = \max\{H(i-1,j-1) + S(X(i),Y(j)), E(i,j), F(i,j)\}
  • Deletion:
E(i+1,j)=max⁡{H(i,j)−go,E(i,j)−ge,0}E(i+1,j) = \max\{H(i,j) - g_o, E(i,j) - g_e, 0\}
  • Insertion:
F(i,j+1)=max⁡{H(i,j)−go,F(i,j)−ge,0}F(i,j+1) = \max\{H(i,j) - g_o, F(i,j) - g_e, 0\}
  • gog_o: gap opening penalty (open a new gap)
  • geg_e: gap extension penalty (extend the existing gap)
  • Banded: ∣i−j∣≤w|i-j| \le w

Interactive DP Table

7 GenDP framework​

  • inter-cell dependency patterns
    • are determined by the recursion rule in the DP kernel.
    • configure the processing element (PE) interconnection and generate the control instructions.
  • intra-cell data-flow graph for objective Function
    • is mapped to compute units based on the DPMap algorithm.
    • The compute instructions are generated based on the mapping results.

1). 2D DP inter-cell dependency​

two-dimensional wavefront dependence

Interactive 2D DP Table: BSW PE

Interactive 2D DP Table: BSW PE + FIFO

Interactive 2D DP Table: BSW PE + FIFO + EF

Interactive 2D DP Table: BSW PE + FIFO + EF + banded w

2). 1D DP inter-cell dependency​

broadcast + pipeline (full-load operation: data is in the pipeline.)

Interactive 1D DP Table: Chain PE + FIFO

8 Executing model: decoupling control and computation​

Relying solely on a fixed systolic data path cannot meet the demands of various dependency patterns.

Layered execution model: The PE array controls the global data flow and PE initialization; within each PE, a control thread and a computation thread run in parallel, handling data transfer and arithmetic operations respectively.

Instruction preloading and controlled manual instruction generation enable static optimization for each kernel, reducing the overhead of branch and address calculations.

9 DPMap Algorithm​

The DP objective function is represented as a data-flow graph (DFG). The DPMap algorithm generates compute instructions by mapping the DFG to compute units in the PE.

  • node: operator
    • nodes within the subgraphs: ALU
  • edge between the node: dependency between nodes
    • edges within the subgraphs: data movements within CU
    • edges between subgraphs: transfer data through register files (RF)

The compute units (CUs) within the PE are not infinitely flexible. CU employs a 2-level ALU reduction tree. Structural Constraints

The goal of DPMap is to minimize RF access while respecting the structural constraints of the CU.

3 Steps: 1). Partitioning: Isolate those nodes that require dedicated CU resources (multiplication, 4-input operations) and cut off their excessive external connections to reduce the complexity of subsequent grouping.

  • Multiplication: input/output must be passed via register files.
  • 4-input operations(Comparison, MatchScore): input must be passed via register files.
Comparison >  : out = in[0] > in[1] ? in[2] : in[3] 
Comparison == : out = in[0] == in[1] ? in[2] : in[3]
MatchScore    : out = scoretable(in[0], in[1])
S(X(i), Y(j)) = (X(i) == Y(j)) ? matchScore : mismatchScore

2). Seeding: Finding a “convergence point” in DFG: two parent nodes merge into one child node.

  • look for nodes that are suitable for the second level of the ALU reduction tree and name them seeds.

3). Refinement: traverses the DFG in reverse order.

  • After the first two steps, most of the remaining nodes have either only one parent node or only one child node. Refinement pairs them up in groups of two and maps them to a level-2 ALU tree.
  • Organize from the output side toward the input side to ensure that each node can find a suitable partner, so that all subgraphs can fit into CU’s level-2 ALU tree.