TensorTonic
Study Plans
Study Plan
Global-Memory Coalescing Counter
GPU Programming
Easy

Count the cache-line transactions needed for a group of memory accesses. Each lane requests access_width_bytes consecutive bytes from its starting address. For lane iii, aia_iai​ is the start address, WWW is access_width_bytes, LLL is cache_line_bytes, and sis_isi​ and eie_iei​ are its first and last touched line IDs. Floor rounds down.

si=⌊aiL⌋.s_i=\left\lfloor\frac{a_i}{L}\right\rfloor.si​=⌊Lai​​⌋. ei=⌊ai+W−1L⌋.e_i=\left\lfloor\frac{a_i+W-1}{L}\right\rfloor.ei​=⌊Lai​+W−1​⌋.

Each distinct touched line costs one transaction. Let UUU be the number of distinct requested byte addresses across all lanes and CCC be the number of touched lines:

useful_byte_fraction⁡=UCL.\operatorname{useful\_byte\_fraction}=\frac{U}{CL}.useful_byte_fraction=CLU​.

Overlapping requests count shared bytes only once. Return a dictionary containing line_ids as a sorted one-dimensional NumPy int64 array of length C, transaction_count as a Python integer, and useful_byte_fraction as a Python float.

Loading visualization...

Examples

Input: byte_addresses = [0,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,80,84,88,92,96,100,104,108,112,116,120,124], access_width_bytes = 4, cache_line_bytes = 128

Output: {"line_ids":[0],"transaction_count":1,"useful_byte_fraction":1}

Explanation: The 32 adjacent four-byte requests cover exactly one 128-byte cache line, so every transferred byte is useful.

Input: byte_addresses = [0,1024,2048,3072], access_width_bytes = 4, cache_line_bytes = 128

Output: {"line_ids":[0,8,16,24],"transaction_count":4,"useful_byte_fraction":0.03125}

Input: byte_addresses = [126], access_width_bytes = 4, cache_line_bytes = 128

Output: {"line_ids":[0,1],"transaction_count":2,"useful_byte_fraction":0.015625}

Hint 1

Python sets discard duplicate byte addresses.

Hint 2

np.unique returns sorted distinct line IDs.

Requirements

  • Use NumPy for the returned line-ID array and exact integer arithmetic for addresses and counts.
  • Include every line touched by an access, including accesses crossing line boundaries.
  • Do not modify the input array.

Constraints

  • byte_addresses is a one-dimensional NumPy int64 array with 1 to 32 nonnegative start addresses.
  • access_width_bytes is a Python integer from 1 through 256, defaulting to 4.
  • cache_line_bytes is a positive Python integer, defaulting to 128.
  • The address array may be noncontiguous.
Try Similar Problems
Shared-Memory Bank Conflict AnalyzerEasyGPU Occupancy CalculatorMediumMeasure Kernel Timeline UtilizationMediumOrthogonalize a Muon Momentum UpdateEasyPerform Stable Exact DeduplicationEasyPatchify a Batch of ImagesEasyMixed-Precision Training Memory AccountantEasyAccount for ZeRO Memory by StageEasyImplement Symmetric INT8 QuantizationEasyEstimate Model Memory and Minimum GPU CountEasyImplement Per-Channel Weight QuantizationMediumAnalyze Prefill and Decode with the Roofline ModelMedium

Accepts: array

Accepts: number

Accepts: number

You must run your code first.

Global-Memory Coalescing Counter

GPU Programming
Easy

Count the cache-line transactions needed for a group of memory accesses. Each lane requests access_width_bytes consecutive bytes from its starting address. For lane iii, aia_iai​ is the start address, WWW is access_width_bytes, LLL is cache_line_bytes, and sis_isi​ and eie_iei​ are its first and last touched line IDs. Floor rounds down.

si=⌊aiL⌋.s_i=\left\lfloor\frac{a_i}{L}\right\rfloor.si​=⌊Lai​​⌋. ei=⌊ai+W−1L⌋.e_i=\left\lfloor\frac{a_i+W-1}{L}\right\rfloor.ei​=⌊Lai​+W−1​⌋.

Each distinct touched line costs one transaction. Let UUU be the number of distinct requested byte addresses across all lanes and CCC be the number of touched lines:

useful_byte_fraction⁡=UCL.\operatorname{useful\_byte\_fraction}=\frac{U}{CL}.useful_byte_fraction=CLU​.

Overlapping requests count shared bytes only once. Return a dictionary containing line_ids as a sorted one-dimensional NumPy int64 array of length C, transaction_count as a Python integer, and useful_byte_fraction as a Python float.

Loading visualization...

Examples

Input: byte_addresses = [0,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,80,84,88,92,96,100,104,108,112,116,120,124], access_width_bytes = 4, cache_line_bytes = 128

Output: {"line_ids":[0],"transaction_count":1,"useful_byte_fraction":1}

Explanation: The 32 adjacent four-byte requests cover exactly one 128-byte cache line, so every transferred byte is useful.

Input: byte_addresses = [0,1024,2048,3072], access_width_bytes = 4, cache_line_bytes = 128

Output: {"line_ids":[0,8,16,24],"transaction_count":4,"useful_byte_fraction":0.03125}

Input: byte_addresses = [126], access_width_bytes = 4, cache_line_bytes = 128

Output: {"line_ids":[0,1],"transaction_count":2,"useful_byte_fraction":0.015625}

Hint 1

Python sets discard duplicate byte addresses.

Hint 2

np.unique returns sorted distinct line IDs.

Requirements

  • Use NumPy for the returned line-ID array and exact integer arithmetic for addresses and counts.
  • Include every line touched by an access, including accesses crossing line boundaries.
  • Do not modify the input array.

Constraints

  • byte_addresses is a one-dimensional NumPy int64 array with 1 to 32 nonnegative start addresses.
  • access_width_bytes is a Python integer from 1 through 256, defaulting to 4.
  • cache_line_bytes is a positive Python integer, defaulting to 128.
  • The address array may be noncontiguous.
Try Similar Problems
Shared-Memory Bank Conflict AnalyzerEasyGPU Occupancy CalculatorMediumMeasure Kernel Timeline UtilizationMediumOrthogonalize a Muon Momentum UpdateEasyPerform Stable Exact DeduplicationEasyPatchify a Batch of ImagesEasyMixed-Precision Training Memory AccountantEasyAccount for ZeRO Memory by StageEasyImplement Symmetric INT8 QuantizationEasyEstimate Model Memory and Minimum GPU CountEasyImplement Per-Channel Weight QuantizationMediumAnalyze Prefill and Decode with the Roofline ModelMedium

Accepts: array

Accepts: number

Accepts: number

You must run your code first.