Modern Multicore Processors

A Modern Multi-core Processor #

Part 1: Speeding up an example sine program #

Computes sin across an array of float values using a Taylor series expansion

void sinx(int N, int terms, float *x, float *y) {
    for (int i = 0; i < N; i++) {
        float value = x[i];
        float numer = x[i] * x[i] * x[i];
        int denom = 6; // 3!
        int sign = -1;

        for (int j = 1; j <= terms; j++) {
            value += sign * numer / denom;
            numer *= x[i] * x[i];
            denom *= (2 * j + 2) * (2 * j + 3);
            sign *= -1;

        y[i] = value;

This compiles to some assembly:

ld  r0, addr[r1] // x[i]
mul r1, r0, r0
mul r1, r1, r0
// ...
st  addr[r2], r0 // y[i]

Pre-multicore era processor #

  • Majority of chip transistors used to perform ops that help make single instruction streams run fast
    • Out of order control logic
    • Fancy branch predictor
    • Memory prefetcher
    • More transistors = larger cache

Multicore-era processor #

  • Idea: use transistor count to add more cores to the processor
    • Simple cores: each core maybe slowre at running a single instruction stream than original fancy core (e.g. 25% slower)
    • However, with two cores: 2 * 0.75 = 1.5 = 50% speedup!
  • However: C program will compile to single instruction stream that runs on only one thread on one core

Transforming a program to multicore #

typedef struct {
    int N,
    int terms;
    float *x;
    float *y;
} my_args;

void my_thread_func(my_args *args) {
    sinx(args->N, args->terms, args->x, args->y); // do work

void parallel_sinx(int N, int terms, float *x, float *y) {
    std::thread my_thread;
    my_args args;
    args.N = N/2;
    args.terms = terms;
    args.x = x;
    args.y = y;

    my_thread = std::thread(my_thread_func, &args); // launch thread
    sinx(N - args.N, terms, x + args.N, y + args.N); // do work on main thread

    /* NOTE: because of this waiting, we can only ever get 2x speedup!! */
    my_thread.join(); // wait for thread to complete

Data-parallel expressions #

void sinx(int N, int terms, float *x, float *y) {
    // original:
    // for (int i = 0; i < N; i++) {

    // new: fictituous forall construct that tells the compiler
    // that each of these iterations are independent
    forall (int i from 0 to N) {
        float value = x[i];
        float numer = x[i] * x[i] * x[i];
        int denom = 6; // 3!
        int sign = -1;

        for (int j = 1; j <= terms; j++) {
            value += sign * numer / denom;
            numer *= x[i] * x[i];
            denom *= (2 * j + 2) * (2 * j + 3);
            sign *= -1;

        y[i] = value;

With such a construct, a compiler might be able to autogenerate threaded code.

SIMD processing #

  • Single instruction, multiple data
  • Additional execution units (ALUs) increase compute capability
  • Idea: Amortize cost/complexity of managing an instruction stream across many ALUs
    • Same instruction broadcast to all ALUs
    • Operation executed in parallel on all ALUs
  • e.g. Original scalar program processes one array element using scalar instructions on scalar registers
  • Instead, use vector operations (i.e. __m256 types and __mm256 arith and load operations)
    • These are intrinsic datatypes and functions available to C programmers
    • These operate on vectors of eight 32-bit values (e.g. vector of 8 floats)
    • Compiled program processes eight array elements simultaneously using vector instructions on 256-bit vector register
  • Note: with Data-parallel expression example code, the forall abstraction can also facilitate autogeneration of SIMD instructions
    • In addition to multi-core parallel code!

Conditional execution with SIMD #

Consider the following example

forall (int i from 0 to N) {
    float t = x[i];
    // unconditional code
    if (t > 0.0) {
        t = t * t;
        t = t * 50.0;
        t = t + 100.0;
    } else {
        t = t + 30.0;
        t = t / 10.0;

    // resume unconditional code
    y[i] = t;
  • How to process this on a vector-only CPU?
    • Mask (discard) output of ALU
    • Run all with true branches, discard output of false branches
    • Run all with false branches, discard output of true branches
    • Worst case: 1/8 of peak performance
      • Can create this by making the if branch extremely costly, but processor is still forced to send all the branch that way
        if (i == 0) {
        } else {

SIMD jargon #

  • Instruction stream coherence (“coherent execution”)
    • Property of a program where same instruction stream applies to many data elements
    • NECESSARY for SIMD processing to be used efficiently
    • NOT NECESSARY for efficient parallelization across different cores
  • Divergent execution
    • Lack of instruction stream coherence

Modern CPU examples of SIMD #

  • AVX2 (Intel): 256b operations: 8x32bit or 4x64bit
  • AVX512 (Intel): 512b: 16x32bit
  • ARM Neon: 128b: 4x32bit
  • Instructions generated by complier
    • Requested by programmer using intrinsics
    • Or parallel language semantics (e.g. forall)
    • Inferred by dependency analysis of loops by auto-vectorizing compiler
  • Explicit SIMD: SIMD parallelization performed at compile time
    • SIMD instructions in binary itself (e.g., vstoreps, vmulps, etc.)
Example: Intel i7-7700K (Kaby Lake, 2017) #
  • 4 core CPU
  • Three 8-wide SIMD ALUs per core for AVX2
  • 4 cores x 8-wide SIMD * 3 * 4.2 GHz = 400 GFLOPs

SIMD on GPUs #

  • “Implicit SIMD”
    • Compiler generates binary with scalar instructions
    • But N instances of program always run together on processor
    • Hardware, not compiler, responsible for executing same instruction on multiple program instances on different data on SIMD ALUs
  • SIMD width of most modern GPUs ranges from 8 to 32
    • Divergent execution can result in 1/32 of peak capacity

Part 2: accessing memory #

Load/store: instructions that access memory #

// load 4b value in memory starting from address stored by register r2
// and put it into register r0
ld r0 mem[r2]

// store 4b value in r0 into address stored by register r2
st r0 mem[r2]

Memory terminology #

  • Memory address space
    • Memory organized as sequence of bytes
    • Each byte identified by address in memory
    • Address space: total addressable memory of a program
  • Memory access latency
    • Amount of time it takes memory system to provide data to the processor
    • e.g. 100 clock cycles, 100 nsec
  • Stalls
    • A processor “stalls” when it cannot run the next instruction in an instruction stream due to dependency on a previous incomplete instruction
    • e.g. Accessing memory can cause stalls
      ld r0 mem[r2]
      ld r1 mem[r3]
      // Dependency: cannot execute `add` instruction until data 
      // from mem[r2] and mem[r3] have been loaded from memory
      add r0, r0, r1
    • Memory access times: ~hundreds of cycles
      • Measure of latency

Caches #

  • On-chip storage that maintains copy of subset of values in memory
  • Address is “in the cache”: processor can load and store address more quickly than if data resided in memory
  • Hardware implementation detail that does not impact program output; only performance
  • For this class, abstraction: assume cache of size N keeps last N addresses accessed
    • “LIFO” policy: on each memory access, throw out oldest data in cache to make room for newly accessed data
    • In real world, other policies:
      • Direct mapped cache
      • Set-associative cache
      • Cache line
  • Reduce length of stalls and memory access latency
    • Specifically: when accessing data that had recently been accessed
  • e.g. Data access times, Intel Kaby Lake (2017)
    • L1 cache: 4 cycles
    • L2 cache: 12 cycles
    • L3 cache: 38 cycles
    • DRAM: best case ~248 cycles

Data prefetching #

  • Logic on modern CPUs for guessing what data will be accessed in the future
    • Prefetch this data into caches
    • Dynamically analyze program memory access patterns to make predictions
  • Reduces stalls since data is already resident in cache when accessed
    • However: can reduce perf. if guess is wrong (consumes bandwidth, pollutes caches)

Multithreading to reduce stalls #

  • Interleave processing of multiple threads on same core to hide stalls
    • Can’t make process on one thread? Work on another one
    • Once hitting a stall on one thread, immediately switch over another one
  • Idea: potentially increase time to complete a single thread’s work in order to increase overall system throuput when running multiple threads
  • However: this requires storing execution contexts
    • Tradeoff between memory caching and storing these execution contexts
  • Takeaway: a processor with multiple HW threads has the ability to avoid stalls by interleaving executions
    • This doesn’t affect mem. access latency; it just improves processor utilization

Hardware-supported multithreading #

  • Core manages execution contexts for multiple threads
  • Interleaved multi-threading
  • Simultaneous multi-threading (SMT)
    • e.g. Intel Hyper-Threading

Broader takeaway: can combine each of these parallelism constructs!

  • This is what modern chips (e.g., Intel Skylake/Kaby Lake, Nvidia GPUs) do

Latency and Bandwidth #

  • Memory bandwidth: rate at which memory system can provide data to a processor (e.g., 20 GB/s)
    • Execution speed is often limited by available bandwidth
    • e.g. data transfer speed = 8 bytes per clock: then simple math adds (1 add per clock) can create up to 3 outstanding load requests
    • This is called bandwidth-bound execution: instruction throughput limited by bandwidth, not latency or outstanding requests etc.
    • Influences chip design: modern GPUs place memory on or near chip