Tutorial
We provide 10 benchmark applications that illustrate how DynaSOAr is used. Some of these applications have visualizations, which make it easier to analyze the effect of application parameters. In the following, we are building and running wator, a simple fish-and-sharks simulation in which fish and shark objects are dynamically allocated and destroyed.
All benchmark build scripts are located in the build_scripts directory and must be invoked from the DynaSOAr root directory. Before running the scripts, make sure that nvcc is available or set the correct path in build_scripts/nvcc.sh.
We analyze the wator benchmark in this section. The source code of this benchmark is located in the example/wa-tor directory. This benchmark has three/four classes: Agent, Fish, Shark (, Cell).
We compile wator as follows:
$ build_scripts/build_wa_tor.sh
Certain parameters such as the benchmark size or the allocator can be modified. (Check -? option.) We first take a look at the visualization to get a first impression of the benchmark.
$ build_scripts/build_wa_tor.sh -r -x 500 -y 500
$ build_scripts/wator_dynasoar_no_cell
We provide four variant of wator:
-
wator_dynasoar: Runs with the selected allocator (DynaSOAr unless overridden.) -
wator_dynasoar_no_cell: Same as above, butCellobjects are statically allocated since the cell structure does not change in the benchmark. This variant has only 3 classes instead of 4. We used this variant for our benchmarks. -
wator_baseline_aos: AOS baseline without any dynamic allocation. -
wator_baseline_soa: SOA baseline without any static allocation.
Now let us try to understand how dynamic allocation is used in this benchmark. Take a look at the header file example/wa-tor/dynasoar_no_cell/wator.h which defines the three classes Agent, Fish and Shark. When we build the benchmark in debug mode, we can see how DynaSOAr allocates objects of these types.
$ build_scripts/build_wa_tor.sh -d -x 500 -y 500
$ bin/wator_dynasoar_no_cell
First, we get some information about our platform. We are running the benchmark on a GeForce 940MX at the moment.
Current Device Number: 0
Device name: GeForce 940MX
Memory Clock Rate (KHz): 1001000
Memory Bus Width (bits): 64
Peak Memory Bandwidth (GB/s): 16.016000
Total global memory: 2100.232192 MB
Available (free) global memory: 923.860992 MB
What follows is an overview of the memory usage of DynaSOAr.
┌───────────────────────────────────────────────────────────────────────┐
│ Smallest block type: 4Fish │
│ Max. #objects: 262144 │
│ Block size: 3904 bytes │
│ #Blocks: 4096 │
│ #Bitmap levels: 2 │
│ Data buffer size: 000015.250000 MB │
│ Allocator overead: 000000.114670 MB + block overhead │
│ Total memory usage: 000015.364670 MB │
└───────────────────────────────────────────────────────────────────────┘
We can see from here that:
- The smallest class in our system is
Fish. This is important because block capacities are determined by the size of the smallest type. - We configured the allocator such that it can allocate up to 262144 objects of the smallest type
Fish. We can change the variablekNumObjectsinexample/wa-tor/configuration.hto change this value. This number must a multiple of 64. - The size of a block is 3904 bytes (see calculation later...).
- The heap consists of 262144 / 64 = 4096 blocks.
- The hierarchical bitmaps of this allocator (e.g., free block bitmap, allocated block bitmaps) have ceil(log_64(4096)) = 2 levels.
- The size of all blocks is 3904 B * 4096 = 15.25 MiB.
- The size of all block bitmaps is 0.115 MiB.
- The total memory usage of the allocator (including all of its allocations) is 15.4 MiB.
Note that the capacity/heap size of the allocator can currently not be specified in bytes. Instead, we specify the heap size via the number of objects of the smallest type in the system. We currently have to launch the program in debug mode to see how many bytes that equates to. This is just a matter of the API and will change in future versions of DynaSOAr.
Now let us take a look at the classes in our application, starting with class Agent. This class is the first class that was passed as a template argument to SoaAllocator in the header file, which is why it appears first and has a type ID of 0.
┌───────────────────────────────────────────────────────────────────────┐
│ Block stats for 5Agent (type ID 0) │
├────────────────────┬──────────────────────────────────────────────────┤
│ #fields │ 3 │
│ #objects / block │ 64 │
│ block size │ 3648 bytes │
│ base class │ v │
│ is abstract │ 1 │
│ data seg. [64] sz │ 3584 bytes │
│ (unpadded) │ 3584 bytes │
│ (simple sz) │ 3584 bytes │
│ (padding waste) │ 0 bytes │
│ data seg. [ 1] sz │ 64 bytes │
│ (unpadded) │ 56 bytes │
│ data seg. [64] sz │ 3584 bytes │
│ (unpadded) │ 3584 bytes │
├────────────────────┴──────────────────────────────────────────────────┤
│ Fields │
├───────┬─────────────────┬───────────────────────┬──────────┬──────────┤
│ Index │ Def. Class │ Type │ Size │ Offset │
├───────┼─────────────────┼───────────────────────┼──────────┼──────────┤
│ 2 │ 5Agent │ i │ 4 │ 52 │
│ 1 │ 5Agent │ i │ 4 │ 48 │
│ 0 │ 5Agent │ 17curandStateXORWOW │ 48 │ 0 │
├───────┼─────────────────┼───────────────────────┼──────────┼──────────┤
│ Σ │ │ │ 56 │ │
└───────┴─────────────────┴───────────────────────┴──────────┴──────────┘
From here we can see that:
- The class has 3 field: Two fields of type
int(i) and one field of typecurandStateXORWOW(defined ascurandState_tin the source code, which is provided by the cuRAND library). Note that DynaSOAr does not know anything about the typecurandState_t. It is probably a struct with multiple fields, but we do not change its layout. - The class is abstract. (See
static const bool kIsAbstract = true;in the header file.) - The block capacity (
#objects / block) has no meaning in abstract classes. - The class does not inherit from another class. (Base class
v=void.) - The size of the data segment is also not important for abstract classes.
The next two classes are non-abstract classes. Let us take a look at class Shark.
┌───────────────────────────────────────────────────────────────────────┐
│ Block stats for 5Shark (type ID 2) │
├────────────────────┬──────────────────────────────────────────────────┤
│ #fields │ 5 │
│ #objects / block │ 60 │
│ block size │ 3904 bytes │
│ base class │ 5Agent │
│ is abstract │ 0 │
│ data seg. [60] sz │ 3840 bytes │
│ (unpadded) │ 3840 bytes │
│ (simple sz) │ 3840 bytes │
│ (padding waste) │ 0 bytes │
│ data seg. [ 1] sz │ 64 bytes │
│ (unpadded) │ 64 bytes │
│ data seg. [64] sz │ 4096 bytes │
│ (unpadded) │ 4096 bytes │
├────────────────────┴──────────────────────────────────────────────────┤
│ Fields │
├───────┬─────────────────┬───────────────────────┬──────────┬──────────┤
│ Index │ Def. Class │ Type │ Size │ Offset │
├───────┼─────────────────┼───────────────────────┼──────────┼──────────┤
│ 1 │ 5Shark │ j │ 4 │ 60 │
│ 0 │ 5Shark │ j │ 4 │ 56 │
│ 2 │ 5Agent │ i │ 4 │ 52 │
│ 1 │ 5Agent │ i │ 4 │ 48 │
│ 0 │ 5Agent │ 17curandStateXORWOW │ 48 │ 0 │
├───────┼─────────────────┼───────────────────────┼──────────┼──────────┤
│ Σ │ │ │ 64 │ │
└───────┴─────────────────┴───────────────────────┴──────────┴──────────┘
This class inherits from Agent, so those classes are repeated in here. The capacity of blocks of type Shark is 60. (The capacity of the smallest type in the system, Fish in this example, is always 64.) The size of the data segment of the block is 3840 B, which is the sum of all SOA arrays (size 60). Sometimes, the data segment must be larger due to padding of SOA arrays.
Finally, we can see some statistics about the state of the allocator. The benchmark code prints statistics after every iteration when built in debug mode. Note that this slows down the allocator significantly, so do not use debug mode for measuring performance.
┌────┬──────────┬──────────┬──────────┬┬──────────┬──────────┬──────────┐
│ Ty │ #B_alloc │ #B_leq50 │ #B_activ ││ #O_alloc │ #O_used │ O_frag │
├────┼──────────┼──────────┼──────────┼┼──────────┼──────────┼──────────┤
│ fr │ 1320 │ n/a │ n/a ││ n/a │ n/a │ n/a │
│ 0 │ 0 │ 0 │ 0 ││ 0 │ 0 │ 0.000000 │
│ 1 │ 2224 │ 0 │ 2141 ││ 142336 │ 133631 │ 0.061158 │
│ 2 │ 552 │ 0 │ 411 ││ 33120 │ 12478 │ 0.623249 │
│ Σ │ 2776 │ 0 │ 2552 ││ 175456 │ 146109 │ 0.167261 │
└────┴──────────┴──────────┴──────────┴┴──────────┴──────────┴──────────┘
We can read these statistics as follows.
- The
frline shows the number of blocks that arefree(not allocated). There are 1320 free blocks. - There is one line for every type. The number in the first column is the type ID (
0=Agent,1=Fish,2=Shark). -
B_allocis the number of allocated blocks,B_activeis the number of active blocks,O_allocis the number of allocated object slots (all object slots of allocated blocks) andO_usedis the number of object slots that actually contain an object. We can calculate the fragmentation from the last two values as defined in the paper:(O_alloc - O_used) / O_alloc. - There are no objects of abstract classes, so all values for class
Agentare0.
If we watch these statistics for a while, we see that the fragmentation rate is pretty high around iterations 60-80. Sometimes over 80%. We can see this fragmentation spike in the Wa-Tor figures in the paper.
Now let us compare the performance of DynaSOAr and mallocMC.
$ build_scripts/build_wa_tor.sh -x 300 -y 300 -a dynasoar
$ bin/wator_dynasoar_no_cell
634949, 159514
$ build_scripts/build_wa_tor.sh -x 300 -y 300 -a mallocmc
$ bin/wator_dynasoar_no_cell
2123027, 1344489
We ran the benchmark with a very small problem size. If no problem size is specified, the default problem size (also used in the paper) is used. The first number is the overall benchmark running time. The second number is the time spent on parallel enumeration. We should substract this number from the first one to allow for a fair comparison (see paper).
With DynaSOAr, the benchmark finishes in 475435 microseconds (0.475s). With mallocMC, the benchmark runs for 778538 microseconds (0.779s). We could repeat this experiment with other allocators (bitmap, cuda, halloc).
If we increase the problem size, it may also be necessary to increase the heap size to ensure that the allocator does not run out of memory. If DynaSOAr runs out of memory, it currently goes into an infinite loop (see algorithm in the paper). If the other allocators run out of memory, the program usually crashes.
We can increase the heap size of dynasoar and bitmap by modifying the first template argument to SoaAllocator. In the benchmarks, this value is stored in the configuration.h file (variable kNumObjects). For the other allocators, this value is specified in bytes in example/configuration/allocator_interface_adapter.h (variable kMallocHeapSize).