Loading page…
Master the fundamental concepts of cache optimization through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksStandard BFS with a FIFO queue chases pointers through adjacency lists, scattering memory access. Level-synchronous BFS batches all vertices at frontier depth d before moving to d+1, improving locality when you store edges in arrays and visit vertices in sorted order.
Keep current_level[] and next_level[] arrays. For each vertex in the current level, scan its edge range [offset[v], offset[v+1]) in one contiguous block.
cLoading…
Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
You will implement level-by-level BFS on a CSR graph and compare against a queue-based version. This exercise asks you to explain which representation reduced cache misses.
BFS over a large graph is usually memory-bound. Every dequeued vertex touches its CSR row pointers, its slice of the neighbour array, and the visited entries of its neighbours. When vertex ids are scattered, each of those touches lands on a different cache line. Implement BFS on a CSR graph, simulate its memory accesses in a small cache, and then relabel the vertices in BFS order, which is the classic locality-improving reordering, to measure how much it helps.
cLoading…
row_ptr[0..N] and col_idx[], with each adjacency list sorted ascending. BFS visits neighbours in that order.row_ptr (N+1 entries), col_idx (2 × edges), visited (N), queue (N).queue[head], row_ptr[v] and row_ptr[v+1].col_idx[k], then visited[w] (a single access even if w gets marked); if w is new, write queue[tail].cost. Misses are counted per array.nodes: 1..4096, edge U V: rejected (bad or equal endpoints), grid: too big, grid: scramble factor P must be coprime with N (the grid is still built, unscrambled), start: no such node, and cache: invalid.cLoading…
Input:
cLoading…
Output:
cLoading…
Hidden tests cover relabelling a scrambled grid (misses fall sharply), an unscrambled grid, a disconnected graph where some nodes are never reached, a different start vertex, a larger cache, and invalid input.