View on GitHub

SKA

The Static Kernel Analyzer (SKA)

Download this project as a .zip file Download this project as a tar.gz file

What is SKA?

The static kernel analyzer (SKA) combines a static, linear pipeline simulator (similar to the IBM spu_timing tool) with architectural heuristics to model in-order instruction issue and pipeline behavior. Pipeline simulations take as input the intermediate representation (IR) from Low-Level Virtual Machine (LLVM). LLVM and LLVM IR are adopted standards in the HPC community, allowing SKA to support a wide range of source inputs. SKA also has support for the upcoming OpenCL Standard Portable Intermediate Representation (SPIR), which is based on LLVM IR version 3.1. Support for OpenCL kernel source input (in the form of SPIR) allows SKA to model a rich variety of important modern computing architectures, and provides users with a new paradigm for application optimization and design.

The underlying hardware properties accessed by SKA during pipeline simulation are user-defined, allowing for both modeling of existing processors, and experimentation with novel resource provisioning. Thus, SKA can be employed either as an analysis tool for code optimization, or as a co-design tool to aid in the creation of new processor configurations.

Users can visualize the output of SKA pipeline simulations with the skaview program. The novel view representations in skaview give the user both detailed clock-for-clock execution information, as well as intuitive slope and graph views for high-level detection of serious data and structural hazards.

Pipeline Simulator

The primary functionality of ska is as a pipeline simulator of LLVM IR. The below image shows the an annotated screen shot from skaview:

Pipeline Simulation Detail

From left to right, this images shows the issue cycle of each instruction, the logic unit on which it executed (including multiple issue flags: D indicates dual-issue), the pipeline progress (dashes represent stalls) and the LLVM IR instruction that was executed.

Generating Simulations

To create output suitable for viewing in skaview, begin with the source file that you wish to analyze. In this example, we use a simple saxpy update:

for(i=0; i<N; ++i) {
   y[i] = alpha*x[i] + y[i];
} // for

Use the skair script on your source file to generate LLVM IR:

% skair saxpy.c

The skair script is just a wrapper for one of the GNU compilers (gcc, g++ or gfortran) with added flags to use the dragonegg plugin, so you can add any flags that you need to compile your code, e.g.,

% skair -O3 -I/usr/include/special -DMY_DEFINE=defined -Wall -msse saxpy.c

will just pass the extra flags onto the compiler.

The skair script outputs LLVM IR suitable for input into ska (the actual simulator executable). The IR looks like this:

; ModuleID = 'saxpy.c'
target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-apple-darwin11"

define void @saxpy(i32 %n, float %alpha, float* nocapture %x, float* nocapture %y) nounwind uwtable {
entry:
  %0 = icmp sgt i32 %n, 0
  br i1 %0, label %"3.lr.ph", label %return

"3.lr.ph":                                        ; preds = %entry
  %1 = bitcast float* %y to i8*
  %2 = bitcast float* %x to i8*
  br label %"3"

"3":                                              ; preds = %"3", %"3.lr.ph"
  %indvars.iv = phi i64 [ 0, %"3.lr.ph" ], [ %indvars.iv.next, %"3" ]
  %3 = shl nsw i64 %indvars.iv, 2
  %4 = getelementptr inbounds i8* %1, i64 %3
  %5 = getelementptr inbounds i8* %2, i64 %3
  %6 = bitcast i8* %5 to float*
  %7 = load float* %6, align 4, !tbaa !0
  %8 = fmul float %7, %alpha
  %9 = bitcast i8* %4 to float*
  %10 = load float* %9, align 4, !tbaa !0
  %11 = fadd float %8, %10
  store float %11, float* %9, align 4, !tbaa !0
  %indvars.iv.next = add i64 %indvars.iv, 1
  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
  %exitcond = icmp eq i32 %lftr.wideiv, %n
  br i1 %exitcond, label %return, label %"3"

return:                                           ; preds = %"3", %entry
  ret void
}

!0 = metadata !{metadata !"alias set 7: float", metadata !1}
!1 = metadata !{metadata !1}

To generate a simulation, call ska with the LLVM IR:

% ska -o saxpy.ska k10.xml saxpy.ll

This command tells ska to output the simulation to saxpy.ska using AMD's K10 architecture (Supported architectures are in the architectures subdirectory of the main project.) Once you have generated an output file, you can view it with skaview:

% skaview saxpy.ska

Slope View

For a complete, more intuitive view of potential stalls in the pipeline, skaview offers a slope view. The images below show the main window, and the main window with the slope view window opened:

Main WindowSlope Window

The slope view plots the pipeline progress as a single-valued function, with a point at the first execution cycle of each instruction. Longer stalls will have nearly zero slope, while multiple issue sections (best) will have up to -(max issue).

Graph View

Sometimes it is useful to view a basic block as a directed acyclic graph (DAG). Because LLVM IR is in static single-assignment (SSA) form it is straightforward to create a graph view of the LLVM instruction dependencies. The image below shows a portion of such a graph:

Graph Window

Metrics

The ska simulator collects statistics during a run. These statistics are used to generate several metrics. Both the statistics and metrics can be viewed from within skaview:

Metrics