CMSC216 Project 5: Heaps and Performance Optimization

Several data structures defined in el_malloc.h should be studied so that one is acquainted with their intent. The following sections outline many of these and show diagrams to indicate transformation the required functions should implement.

Each block of memory tracked by EL Malloc is preceded and succeeded by some bytes of memory for book keeping. These are referred to as the block "header" and "footer" and are encoded in the el_blockhead_t and el_blockfoot_t structs.

// type which is a "header" for a block of memory; containts info on
// size, whether the block is available or in use, and links to the
// next/prev blocks in a doubly linked list. This data structure
// appears immediately before a block of memory that is tracked by the
// allocator.
typedef struct block {
  size_t size;                  // number of bytes of memory in this block
  char state;                   // either EL_AVAILABLE or EL_USED
  struct block *next;           // pointer to next block in same list
  struct block *prev;           // pointer to previous block in same list
} el_blockhead_t;

// Type for the "footer" of a block; indicates size of the preceding
// block so that its header el_blockhead_t can be found with pointer
// arithmetic. This data appears immediately after an area of memory
// that may be used by a user or is free. Immediately after it is
// either another header (el_blockhead_t) or the end of the heap.
typedef struct {
  size_t size;
} el_blockfoot_t;

As indicated, the blocks use doubly linked nodes in the header which will allow easy re-arrangement of the list.

A picture of a block with its header, footer, and user data area is shown below.

One might wonder why the footer appears. In tracking blocks, there will arise the need to work with a block that immediately precedes given block in memory in memory (not the previous in the linked list). The footer enables this by tracking the size of the user block of memory immediately beneath it.

This is illustrated in the diagram below.

This operation is implemented in the function el_block_below(block) and the similar operation el_block_above(block) finds the next header immediately following one in memory.

The following functions use pointer arithmetic to determine block locations from a provided pointer.

el_blockfoot_t *el_get_footer(el_blockhead_t *block);
el_blockhead_t *el_get_header(el_blockfoot_t *foot);
el_blockhead_t *el_block_above(el_blockhead_t *block);
el_blockhead_t *el_block_below(el_blockhead_t *block);

These functions benefit from macros defined in el_malloc.h that are useful for doing pointer operations involving bytes.

// macro to add a byte offset to a pointer, arguments are a pointer
// and a # of bytes (usually size_t)
#define PTR_PLUS_BYTES(ptr,off) ((void *) (((size_t) (ptr)) + ((size_t) (off))))

// macro to add a byte offset to a pointer, arguments are a pointer
// and a # of bytes (usually size_t)
#define PTR_MINUS_BYTES(ptr,off) ((void *) (((size_t) (ptr)) - ((size_t) (off))))

// macro to add a byte offset to a pointer, arguments are a pointer
// and a # of bytes (usually size_t)
#define PTR_MINUS_PTR(ptr,ptq) (((size_t) (ptr)) - ((size_t) (ptq)))

The main purpose of the memory allocator is to track the available and used blocks in explicit linked lists. This allows used and available memory to be distributed throughout the heap. Below are the data structures that track these lists and the global control data structure which houses information for the entire heap.

// Type for a list of blocks; doubly linked with a fixed
// "dummy" node at the beginning and end which do not contain any
// data. List tracks its length and number of bytes in use.
typedef struct {
  el_blockhead_t beg_actual;    // fixed node at beginning of list; state is EL_BEGIN_BLOCK
  el_blockhead_t end_actual;    // fixed node at end of list; state is EL_END_BLOCK
  el_blockhead_t *beg;          // pointer to beg_actual
  el_blockhead_t *end;          // pointer to end_actual
  size_t length;                // length of the used block list (not counting beg/end)
  size_t bytes;                 // total bytes in list used including overhead;
} el_blocklist_t;
// NOTE: total available bytes for use/in-use in the list is (bytes - length*EL_BLOCK_OVERHEAD)

// Type for the global control of the allocator. Tracks heap size,
// start and end addresses, total size, and lists of available and
// used blocks.
typedef struct {
  void *heap_start;             // pointer to where the heap starts
  void *heap_end;               // pointer to where the heap ends; this memory address is out of bounds
  size_t heap_bytes;            // number of bytes currently in the heap
  el_blocklist_t avail_actual;  // space for the available list data
  el_blocklist_t used_actual;   // space for the used list data
  el_blocklist_t *avail;        // pointer to avail_actual
  el_blocklist_t *used;         // pointer to used_actual
} el_ctl_t;

The following diagram shows some of the structure induced by use of a doubly linked lists overlaid onto the heap. The global control structure el_ctl has two lists for available and used space.

The following functions initialize the global control structures, print stats on the heap, and clean up at the end of execution.

int el_init(int max_bytes);
void el_print_stats();
void el_cleanup();

In several structures, there appear pointers named xxx and structs named xxx_actual. For example, in el_blocklist_t:

typedef struct {
  ...
  el_blockhead_t beg_actual;    // fixed node at beginning of list; state is EL_BEGIN_BLOCK
  el_blockhead_t *beg;          // pointer to beg_actual
  ...
} el_blocklist_t;

The intent here is that there will always be a node at the beginning of the doubly linked list to make the programming easier. It makes sense to have an actual struct beg_actual present. However, when working with the list, the address of the beginning node is often referenced making beg useful. In any case, beg will be initialized to &beg_actual as appears in el_init_blocklist().

void el_init_blocklist(el_blocklist_t *list){
  list->beg        = &(list->beg_actual);
  list->beg->state = EL_BEGIN_BLOCK;
  list->beg->size  = EL_UNINITIALIZED;
  ...
}

Similarly, since there will always be an Available List, el_ctl_t has both an avail pointer to the list and avail_actual which is the struct for the list.

A large number of operations in EL Malloc boil down to doubly linked list operations. This includes

• Unlinking nodes from the middle of list during el_free()
• Adding nodes to the beginning of a headed list (allocation and free)
• Traversing the list to print and search for available blocks

Recall that unlinking a node from a doubly linked list involves modifying the previous and next node as in the following.

  node->prev->next = node->next;
  node->next->prev = node->prev;

while adding a new node to the front is typically accomplished via

  node->prev = list->beg;
  node->next = list->beg->next;
  node->prev->next = node;
  node->next->prev = node;

You may wish to review doubly linked list operations and do some reading on lists with "dummy" nodes at the beginning and ending if these concepts are rusty.

The following functions pertain to block list operations.

void el_init_blocklist(el_blocklist_t *list);
void el_print_blocklist(el_blocklist_t *list);
void el_add_block_front(el_blocklist_t *list, el_blockhead_t *block);
void el_remove_block(el_blocklist_t *list, el_blockhead_t *block);

The basic operation of granting memory on a call to el_malloc(size) involves finding an Available Block with enough bytes for the requested amount of memory. In the event that the block is significantly larger than the request and has enough space for a new header and footer, it can be split into two blocks with one granting the user request and another representing the remaining space.

Note that in some cases, blocks cannot be split: below is a diagram showing case analysis for blocks that have sufficient size to meet request but cannot be split. The diagram below illustrates the net result of el_split_block() which may or may not split a block. Keep in mind that any new block created is not assigned to either the Available or Used lists but will be in later functions.

The rough steps for the el_malloc() function are shown below for the case when block splitting occurs.

1. A block that is large enough to split is located and removed from the Available list.
2. If the block is large enough, it is cut into 2 parts: the requested size and the remainder with a head/foot in between; the original block is set to be part of the Used list and the remainder the Available list
3. The blocks are added to the required lists and a pointer to the user data within the now Used block is returned.

The following functions pertain to the location and splitting of blocks in the available list to fulfill allocation requests.

el_blockhead_t *el_find_first_avail(size_t size);
el_blockhead_t *el_split_block(el_blockhead_t *block, size_t new_size);
void *el_malloc(size_t nbytes);

Freeing memory passes in a pointer to the user area that was granted. Immediately preceding this should be a el_blockhead_t and it can be found with pointer arithmetic.

In order to prevent memory from becoming continually divided into smaller blocks, on freeing the system checks to see if adjacent blocks can be merged. Keep in mind that the blocks that can be merged are adjacent in memory, not next/previous in some linked list. Adjacent blocks can be located using el_block_above() and el_block_below().

To merge, the adjacent blocks must both be Available (not Used). A free can then have several cases.

1. The freed block cannot be merged with any others
2. The freed block can be merged with only the block above it
3. The freed block can be merged with only the block below it
4. The freed block can be merged with both adjacent blocks

The diagrams below show two of these cases.

With careful use of the below functions and handling of NULL arguments, all 4 cases can be handled with very little code. Keep in mind that el_block_above()/below() should return NULL if there is no block above or below due to that are being out of the boundaries of the heap.

el_blockhead_t *el_block_above(el_blockhead_t *block);
el_blockhead_t *el_block_below(el_blockhead_t *block);
void el_merge_block_with_above(el_blockhead_t *lower);
void el_free(void *ptr);

El Malloc initializes the heap with just a single page of memory (EL_PAGE_BYTES = 4096 bytes) during el_init(). While good for testing, a real application would need more space than this. The beginnings of heap expansion are provided via the following function.

int el_append_pages_to_heap(int npages);
// REQUIRED
// Attempts to append pages of memory to the heap with mmap(). npages
// is how many pages are to be appended with total bytes to be
// appended as npages * EL_PAGE_BYTES. Calls mmap() with similar
// arguments to those used in el_init() however requests the address
// of the pages to be at heap_end so that the heap grows
// contiguously. If this fails, prints the message
//
//  ERROR: Unable to mmap() additional 3 pages
//
// and returns 1.  Otherwise, adjusts heap size and end for the
// expanded heap. Creates a new block for the freshly allocated pages
// that is added to the available list. Also attempts to merge this
// block with the block below it. Returns 0 on success.
//
// NOTE ON mmap() USAGE: mmap() returns one of three things if a
// specific address is requested (its first argument):
//
// 1. The address requested indicating the memory mapping succeeded
//
// 2. A different address than the one requested if the requeste
//    address is in use
//
// 3. The constant MAP_FAILED if the address mapping failed.
//
// #2 and #3 above should trigger this function to immediate print an
// #error message and return 1 as the heap cannot be made continuous
// #in those cases.

The central idea of the function is to allocate more space for the heap through mmap() calls. Since it is desirable to treat the heap a contiguous block of memory, the calls to mmap() should attempt to map new space for the heap to the el_ctl->heap_end address thereby "appending" the pages the heap.

Here are a few implementation notes.

• In some cases, NULL is passed as the first argument to mmap() as a user program does not care what virtual address the OS uses for pages of memory. However, El Malloc will have specific addresses that it uses for the heap start and expansion.
• Analyze the provided el_init() function which initially uses mmap() to create the heap. Many aspects of the setup function can be transferred here.
• One difference is that while el_init() allocates the heap at EL_HEAP_START_ADDRESS, el_append_pages_to_heap() should map pages starting at the heap end. This will create a continuous virtual memory space for the heap as it expands.
• The Return Value for mmap() is important and will be one of three things as the docs indicate: the requested address, a different address, or MAP_FAILED. The latter two indicate that heap expansion has failed.

Below is the code structure of the EL Malloc library. Some of the functions have been implemented already while those marked REQUIRED must be completed for full credit on the problem.

// el_malloc.c: implementation of explicit list malloc functions.

#include "el_malloc.h"

////////////////////////////////////////////////////////////////////////////////
// Global control functions

el_ctl_t *el_ctl = NULL;

// Global control variable for the allocator. Must be initialized in
// el_init().

int el_init(uint64_t initial_heap_size);
// Create an initial block of memory for the heap using
// mmap(). Initialize the el_ctl data structure to point at this
// block. The initializ size/position of the heap for the memory map
// are given in the argument symbol and EL_HEAP_START_ADDRESS.
// Initialize the lists in el_ctl to contain a single large block of
// available memory and no used blocks of memory.

void el_cleanup();
// Clean up the heap area associated with the system which unmaps all
// pages associated with the heap.

////////////////////////////////////////////////////////////////////////////////
// Pointer arithmetic functions to access adjacent headers/footers

el_blockfoot_t *el_get_footer(el_blockhead_t *head);
// Compute the address of the foot for the given head which is at a
// higher address than the head.

el_blockhead_t *el_get_header(el_blockfoot_t *foot);
// REQUIRED
// Compute the address of the head for the given foot which is at a
// lower address than the foot.

el_blockhead_t *el_block_above(el_blockhead_t *block);
// Return a pointer to the block that is one block higher in memory
// from the given block.  This should be the size of the block plus
// the EL_BLOCK_OVERHEAD which is the space occupied by the header and
// footer. Returns NULL if the block above would be off the heap.
// DOES NOT follow next pointer, looks in adjacent memory.

el_blockhead_t *el_block_below(el_blockhead_t *block);
// REQUIRED
// Return a pointer to the block that is one block lower in memory
// from the given block.  Uses the size of the preceding block found
// in its foot. DOES NOT follow block->next pointer, looks in adjacent
// memory. Returns NULL if the block below would be outside the heap.
// 
// WARNING: This function must perform slightly different arithmetic
// than el_block_above(). Take care when implementing it.

////////////////////////////////////////////////////////////////////////////////
// Block list operations

void el_print_blocklist(el_blocklist_t *list);
// Print an entire blocklist. The format appears as follows.
//
// {length:   2  bytes:  3400}
//   [  0] head @ 0x600000000000 {state: a  size:   128}
//   [  1] head @ 0x600000000360 {state: a  size:  3192}
//
// Note that the '@' column uses the actual address of items which
// relies on a consistent mmap() starting point for the heap.

void el_print_block(el_blockhead_t *block);
// Print a single block during a sequential walk through the heap

void el_print_heap_blocks();
// Print all blocks in the heap in the order that they appear from
// lowest addrses to highest address

void el_print_stats();
// Print out stats on the heap for use in debugging. Shows the
// available and used list along with a linear walk through the heap
// blocks.

void el_init_blocklist(el_blocklist_t *list);
// Initialize the specified list to be empty. Sets the beg/end
// pointers to the actual space and initializes those data to be the
// ends of the list.  Initializes length and size to 0.

void el_add_block_front(el_blocklist_t *list, el_blockhead_t *block);
// REQUIRED
// Add to the front of list; links for block are adjusted as are links
// within list.  Length is incremented and the bytes for the list are
// updated to include the new block's size and its overhead.

void el_remove_block(el_blocklist_t *list, el_blockhead_t *block);
// REQUIRED
// Unlink block from the list it is in which should be the list
// parameter.  Updates the length and bytes for that list including
// the EL_BLOCK_OVERHEAD bytes associated with header/footer.

////////////////////////////////////////////////////////////////////////////////
// Allocation-related functions

el_blockhead_t *el_find_first_avail(size_t size);
// REQUIRED
// Find the first block in the available list with block size of at
// least `size`.  Returns a pointer to the found block or NULL if no
// block of sufficient size is available.

el_blockhead_t *el_split_block(el_blockhead_t *block, size_t new_size);
// REQUIRED
// Set the pointed to block to the given size and add a footer to
// it. Creates another block above it by creating a new header and
// assigning it the remaining space. Ensures that the new block has a
// footer with the correct size. Returns a pointer to the newly
// created block while the parameter block has its size altered to
// parameter size. Does not do any linking of blocks nor changes of
// list membership: this is done elsewhere.  If the parameter block
// does not have sufficient size for a split (at least new_size +
// EL_BLOCK_OVERHEAD for the new header/footer) makes no changes tot
// the block and returns NULL indicating no new block was created.

void *el_malloc(size_t nbytes);
// REQUIRED
// Return pointer to a block of memory with at least the given size
// for use by the user.  The pointer returned is to the usable space,
// not the block header. Makes use of find_first_avail() to find a
// suitable block and el_split_block() to split it.  Returns NULL if
// no space is available.

////////////////////////////////////////////////////////////////////////////////
// De-allocation/free() related functions

void el_merge_block_with_above(el_blockhead_t *lower);
// REQUIRED
// Attempt to merge the block lower with the next block in
// memory. Does nothing if lower is null or not EL_AVAILABLE and does
// nothing if the next higher block is null (because lower is the last
// block) or not EL_AVAILABLE.  Otherwise, locates the next block with
// el_block_above() and merges these two into a single block. Adjusts
// the fields of lower to incorporate the size of higher block and the
// reclaimed overhead. Adjusts footer of higher to indicate the two
// blocks are merged.  Removes both lower and higher from the
// available list and re-adds lower to the front of the available
// list.

void el_free(void *ptr);
// REQUIRED
// Free the block pointed to by the give ptr.  The area immediately
// preceding the pointer should contain an el_blockhead_t with information
// on the block size. Attempts to merge the free'd block with adjacent
// blocks using el_merge_block_with_above(). If called on a NULL
// pointer or the block is not in state EL_USED, prints the error
// 
//   ERROR: el_free() not called on an EL_USED block
// 
// and returns immediately without further action.

////////////////////////////////////////////////////////////////////////////////
// HEAP EXPANSION FUNCTIONS

int el_append_pages_to_heap(int npages);
// REQUIRED
// Attempts to append pages of memory to the heap with mmap(). npages
// is how many pages are to be appended with total bytes to be
// appended as npages * EL_PAGE_BYTES. Calls mmap() with similar
// arguments to those used in el_init() however requests the address
// of the pages to be at heap_end so that the heap grows
// contiguously. If this fails, prints the message
// 
//  ERROR: Unable to mmap() additional 3 pages
// 
// and returns 1.  Otherwise, adjusts heap size and end for the
// expanded heap. Creates a new block for the freshly allocated pages
// that is added to the available list. Also attempts to merge this
// block with the block below it. Returns 0 on success.
// 
// NOTE ON mmap() USAGE: mmap() returns one of three things if a
// specific address is requested (its first argument):
// 
// 1. The address requested indicating the memory mapping succeeded
// 
// 2. A different address than the one requested if the requeste
//    address is in use
// 
// 3. The constant MAP_FAILED if the address mapping failed.
//
// #2 and #3 above should trigger this function to immediate print an
// #error message and return 1 as the heap cannot be made continuous
// #in those cases.

Below is a run showing the behavior of a series of el_malloc() / el_free() calls. They are performed in the provided el_demo.c program.

A problem that occasionally arises in numerical computing when working with Matrices (2D Arrays) is to compute the sums of the Diagonals of a matrix. The main diagonal of a matrix is comprised of all elements at indices (0,0), (1,1), (2,2), and so forth. There are several numbering schemes for diagonals but we will use the one represented in the following diagram which also shows the sums of the diagonals.

A code is provided in the file sumdiag_base.c which computes the sums of diagonals and stores them in a vector. The algorithm does so using the most "natural" approach of walking down each diagonal and totaling its elements then storing the result in the associated vector element. As you survey the code, note the use of various convenience functions such as mget(mat,i,j) and vset(vec,i,x) to interact with the matrix and vector types used.

int sumdiag_BASE_NORMAL(matrix_t mat, vector_t vec) {
  if(vec.len != (mat.rows + mat.cols -1)){
    printf("sumdiag_base: bad sizes\n");
    return 1;
  }
  for(int i=0; i<vec.len; i++){                    // initialize vector of diagonal sums
    VSET(vec,i,0);                                 // to all 0s
  }

  for(int d=0; d < mat.rows; d++){                 // iterate over lower diagonals
    int c = 0;                                     // col always starts at 0 in lower diags
    for(int r=mat.rows-d-1; r<mat.rows; r++,c++){  // work down rows, right cols for same diag
      int el_rc = MGET(mat, r, c);                 // get matrix element on diagonal
      int vec_d = VGET(vec, d);                    // retrieve current sum for diag
      VSET(vec, d, el_rc+vec_d);                   // add on back to the diagonal sum
    }
  }

  int maxdiag = (mat.rows+mat.cols)-1;             // calculate last diagonal
  for(int d=mat.rows; d < maxdiag ; d++){          // iterate starting at first upper diag
    int r = 0;                                     // row always starts at 0 in upper diags
    for(int c=d-mat.cols+1; c<mat.cols; r++,c++){  // work down rows, right cols for same diag
      int el_rc = MGET(mat, r, c);                 // matrix element
      int vec_d = VGET(vec, d);                    // diagonal sum from vector
      VSET(vec, d, el_rc+vec_d);                   // add on to sum
    }
  }
  return 0;                                        // return success
}

While this algorithm is a direct translation of how humans would visually calculate the sums of diagonals for small matrices, it is unfortunately fairly slow when executing on most modern computing systems.

The purpose of this problem is to write sumdiag_OPTM() which is a faster version of the provided sumdiag_BASE() to calculate the sums of diagonals.

Write your code in the file sumdiag_optm.c.

Keep the following things in mind.

1. You will need to acquaint yourself with the functions and types related to matrices and vectors provided in the matvec.h and demonstrated in the baseline function. Understanding the layout of the matrix in memory is essential to unlocking performance.
2. The goal of sumdiag_OPTM() is to exceed the performance of sumdiag_BASE() by as much as possible.
3. To achieve this goal, several optimizations must be implemented and suggestions are given in a later section.
4. There is one additional parameter to the optimized function: sumdiag_OPTM(mat,vec,thread_count). This indicates the number of threads that should be used to compute diagonal sums.
5. Part of your grade will be based on the speed of the optimized code on zaratan.umd.edu. The main routine sumdiag_benchmark.c will be used for this.

Some details are provided in subsequent sections.

The file sumdiag_benchmark.c provides a benchmark for the speed of diagonal summing. It will be used by graders to evaluate the submitted code and should be used during development to gauge performance improvements.

Evaluations will be done on Zaratan compute nodes so make sure to run test your optimized code on Zaratan by running

login-1>> make benchmark
gcc ...
...
timeout 60s ./sumdiag_benchmark
...
RAW POINTS: 37.41
TOTAL POINTS: 35 / 35

This will compile and run your optimized version and report timing information from it that will be part of your score for the problem.

If you are not running on Zaratan, you will see warnings the results may not be trustworthy. This is fine in the development stage but ultimately test your speed on Zaratan.

The output of the sumdiag_benchmark is shown below.

• SIZE: the size of the matrix being used. The benchmark always uses square matrices
• BASE: the time it takes for sumdiag_BASE() to complete.
• #T: number of threads used for running sumdiag_OPTM()
• OPTM: the time it takes for sumdiag_OPTM() to complete.
• SPDUP: the speedup of sumdiag_OPTM() over sumdiag_BASE() which is BASE / OPTM.

• POINTS: earned according to the following code:

      double points = log(speedup_OPTM) / log(2.0);
  

  This scheme means that unless actual optimizations are implemented, 0 points will be scored. Roughly this scores according to a logarithmic scale that is weighted towards more points if speedups at larger sized inputs is achieved.

Below are several demonstration runs of sumdiag_benchmark.

# ###############################################################################
# RUN ON INCORRECT MACHINE (NOT Zaratan nodes), NOTE WARNINGS
homeputer>> make benchmark
timeout --foreground 60s ./sumdiag_benchmark
WARNING: expected host like 'compute-a8-56.zaratan.umd.edu' but got host 'homeputer'
WARNING: ensure you are on a valid machine for the benchmark
WARNING: timing results / scoring will not reflect actual scoring
==== Matrix Diagonal Sum Benchmark Version 6 ====
------ Tuned for zaratan.umd.edu machines -------
Running with 3 sizes and 4 thread_counts (max 8)
  SIZE   BASE #T   OPTM  SPDUP POINTS  TOTAL
  4096  4.086  1  0.762   5.36   2.42   2.42
               2  0.369  11.08   3.47   5.89
               5  0.265  15.41   3.95   9.84
               8  0.184  22.17   4.47  14.31
  8193  5.706  1  1.016   5.62   2.49  16.80
               2  0.492  11.59   3.54  20.33
               5  0.344  16.57   4.05  24.38
               8  0.260  21.98   4.46  28.84
 12705  7.441  1  1.221   6.09   2.61  31.45
               2  0.580  12.82   3.68  35.13
               5  0.405  18.36   4.20  39.33
               8  0.323  23.03   4.53  43.85
RAW POINTS: 43.85
TOTAL POINTS: 35 / 35
WARNING: expected host like 'compute-a8-56.zaratan.umd.edu' but got host 'homeputer'
WARNING: ensure you are on a valid machine for the benchmark
WARNING: timing results / scoring will not reflect actual scoring

# ###############################################################################
# PARTIAL CREDIT RUN
>> ssh login.zaratan.umd.edu
...
login-1>> make benchmark
timeout --foreground 60s ./sumdiag_benchmark
==== Matrix Diagonal Sum Benchmark Version 6 ====
------ Tuned for zaratan.umd.edu machines -------
Running with 3 sizes and 4 thread_counts (max 8)
  SIZE   BASE #T   OPTM  SPDUP POINTS  TOTAL
  4096  1.739  1  0.647   2.69   1.43   1.43
               2  0.648   2.68   1.42   2.85
               5  0.648   2.69   1.43   4.28
               8  0.652   2.67   1.42   5.69
  8193  2.015  1  0.847   2.38   1.25   6.94
               2  0.851   2.37   1.24   8.19
               5  0.850   2.37   1.24   9.43
               8  0.851   2.37   1.24  10.68
 12705  2.180  1  1.017   2.14   1.10  11.77
               2  1.016   2.14   1.10  12.88
               5  1.018   2.14   1.10  13.97
               8  1.015   2.15   1.10  15.08
RAW POINTS: 15.08
TOTAL POINTS: 15 / 35
# ###############################################################################
# FULL CREDIT RUN
>> ssh login.zaratan.umd.edu
...
login-1>> make benchmark
timeout --foreground 60s ./sumdiag_benchmark
==== Matrix Diagonal Sum Benchmark Version 6 ====
------ Tuned for zaratan.umd.edu machines -------
Running with 3 sizes and 4 thread_counts (max 8)
  SIZE   BASE #T   OPTM  SPDUP POINTS  TOTAL
  4096  1.797  1  0.518   3.47   1.80   1.80
               2  0.271   6.62   2.73   4.52
               5  0.120  15.01   3.91   8.43
               8  0.082  21.82   4.45  12.88
  8193  2.056  1  0.680   3.02   1.60  14.47
               2  0.342   6.01   2.59  17.06
               5  0.140  14.70   3.88  20.94
               8  0.091  22.62   4.50  25.44
 12705  2.156  1  0.821   2.63   1.39  26.83
               2  0.410   5.26   2.40  29.23
               5  0.167  12.88   3.69  32.91
               8  0.106  20.30   4.34  37.26
RAW POINTS: 37.26
TOTAL POINTS: 35 / 35

Note that it is possible to exceed the score associated with maximal performance (as seen in the RAW POINTS reported) but no more than the final reported points will be given for the performance portion of the problem.

Achieving very high speedup and significantly exceeding the max score may garner some MAKEUP credit: you'll know you earned this as the benchmark will report as much

As one works on implementing optimizations in sumdiag_OPTM(), bugs which compute incorrect results are often introduced. To aid in testing, the sumdiag_print() program runs both the BASE and OPTM versions on the same matrix and shows all results. The matrix size is determined from the command line and is printed on the screen to enable hand verification. Examples are below.

>> sumdiag_print                       # show usage: pass mat size and thread_count
usage: sumdiag_print <size> <thread_count>

> ./sumdiag_print 5  1                 # run on a size 5 by 5 matrix with 1 thread
==== Matrix Diagonal Sum Print ====
Matrix:
5 x 5 matrix                           # shows the matrix
   0:    0    1    2    3    4
   1:    5    6    7    8    9
   2:   10   11   12   13   14
   3:   15   16   17   18   19
   4:   20   21   22   23   24

Diagnonal Sums:                        # prints diag sums for BASE/OPTM
[ i]: BASE OPTM
[ 0]:   20   20                        # matching
[ 1]:   36   36
[ 2]:   48   48
[ 3]:   56   56
[ 4]:   60   36 ***                    # not matching: OPTM is buggy
[ 5]:   40   21 ***
[ 6]:   24   10 ***
[ 7]:   12    3 ***
[ 8]:    4    0 ***

Labs and lectures will cover several kinds of optimizations which are useful to improve the speed of sumdiag_OPTM(). Two optimizations are required which are:

1. Re-ordering memory accesses to be as sequential as possible which favors cache. Unless memory access favors cache, it is unlikely that many optimizations will have much effect.
2. Use threads to split up the work of calculating diagonals. The problem parallelized well as worker threads can mostly compute independent results before combining them with the results of other threads.

In most cases, implementing these two correctly will yield full performance points.

Additional optimizations may be performed to further speed up the computations. Some of these are described in Chapter 5 of Bryant/O'Hallaron.

1. Replacing repeated memory references with local non-pointer data which will likely be assigned to registers to alleviate slow-down from memory accesses.
2. Increasing potential processor pipelining by adjusting the destinations of arithmetic operations.
3. Decreasing any unnecessary work such as memory accesses or arithmetic operations.

None of these are required. However, MAKEUP Credit is available for achieving scores that greatly exceed the original baseline version. The benchmark program will check for high scores and give an obvious sign that makeup credit is earned.

1. While optimizing the memory access pattern, it is handy to be able to convert a Row/Column index to a Diagonal number (e.g. Row 3, Col 1 is in Diagonal 2). Research or derive a formula that relates a row/column index to its diagonal number to aid your optimization efforts.
2. Lecture and discussion will provide examples of how to effectively deploy threads and use a mutex to coordinate them. Draw inspiration from those materials for your work.
3. To get the most out of thread performance, code them to compute private partial results. This avoids any unnecessary mutex locking. In most cases, threads will need to update a shared variable so a mutex is needed (in fact required in your solution). However, locking the mutex only once at the end of the thread's work greatly benefit performance over repeated lock/unlock approaches.

Refer to the Project 1 instructions and adapt them for details of how to submit to Gradescope. In summary they are

Command Line Submission

Type make submit to create a zip file and upload it to Gradescope; enter your login information when prompted.

Manual Submission

Type make zip to create pX-complete.zip, transfer this file to a local device, then upload it to the appropriate assignment on Gradescope via the sites web interface.

You may wish to review the policy on late project submission which will cost 1 Engagement Point per day late. No projects will be accepted more than 48 hours after the deadline.

https://www.cs.umd.edu/~profk/216/syllabus.html#late-submission