[Python] Execution times inconsistent with benchmark complexity in gem5 simulation

I'm running the Bubble Sort benchmark on the simplest gem5 architecture model. I used three inputs of size 1000: 1) a worst case (descending order), an average case (random order) and a best case (ascending order).

The results shown on stats.txt are not compatible with the complexity of the cases. The worst case should take longer to run than the average and best case, as its complexity of O(n^2) pitted against O(n), but this is not happening.

Any suggestions on what might be driving gem5 for these results? I've tried AtomicSimpleCPU and TimingSImpleCPU.

TimingSimpleCPU() c clock() function simTicks numCycles simInst
Best Case 1760640 1769385792000 1769385792 18270740
Average Case 1762432 1771194450000 1771194450 18287151
Worst Case 1760000 1768710489000 1768710489 18263273
AtomicSimpleCPU() c clock() function simTicks numCycles simInst
Best Case 31872 32193276000 32193321 18270464
Average Case 32000 32215575000 32215620 18286703
Worst Case 31872 32183116000 32183161 18263098

Find below the Bubble Sort (test.c) and the python gem5 codes.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct timespec start, end;

int arr[1000] = {1, 2, 3, 4, 5, 6, 7, 8,...., 1000}; //best case
//int arr[1000] = {250, 2, 998, 876,...., 27}; //average case
//int arr[1000] = {1000, 999, 998, 997,...., 1}; //worst case
int size = 1000;

int bsort_BubbleSort( int *arr, int bsort_SIZE )
{
int Sorted = 0;
int Temp, Index, i;

for ( i = 0; i < bsort_SIZE - 1; i ++ ) {
Sorted = 1;

for ( Index = 0; Index < bsort_SIZE - 1; Index ++ ) {
if ( Index > bsort_SIZE - i )
break;
if ( arr[ Index ] > arr[Index + 1] ) {
Temp = arr[ Index ];
arr[ Index ] = arr[ Index + 1 ];
arr[ Index + 1 ] = Temp;
Sorted = 0;
}
}

if ( Sorted )
break;
}

return 0;
}

int main() {

clock_t t1, t2;
int i;
float diff;
int array[size];

FILE * pFile;
pFile = fopen ("myfile.txt","w");

t1 = clock();
bsort_BubbleSort(array, size);
t2 = clock();

diff = (((float)t2 - (float)t1));

fprintf (pFile, "%f\n", diff);
fclose(pFile);
return 0;
}


# import the m5 (gem5) library created when gem5 is built
import m5

# import all of the SimObjects
from m5.objects import *

# create the system we are going to simulate
system = System()

# Set the clock frequency of the system (and all of its children)
system.clk_domain = SrcClockDomain()
system.clk_domain.clock = "1GHz"
system.clk_domain.voltage_domain = VoltageDomain()

# Set up the system
system.mem_mode = "atomic"
# system.mem_mode = "timing" # Use timing accesses
system.mem_ranges = [AddrRange("512MiB")] # Create an address range

# Create a simple CPU
# You can use ISA-specific CPU models for different workloads:
# `RiscvTimingSimpleCPU`, `ArmTimingSimpleCPU`.
system.cpu = AtomicSimpleCPU()
# system.cpu = TimingSimpleCPU()

# Create a memory bus, a system crossbar, in this case
system.membus = SystemXBar()

# Hook the CPU ports up to the membus
system.cpu.icache_port = system.membus.cpu_side_ports
system.cpu.dcache_port = system.membus.cpu_side_ports

# create the interrupt controller for the CPU and connect to the membus
system.cpu.createInterruptController()

# For X86 only we make sure the interrupts care connect to memory.
# Note: these are directly connected to the memory bus and are not cached.
# For other ISA you should remove the following three lines.
system.cpu.interrupts[0].pio = system.membus.mem_side_ports
system.cpu.interrupts[0].int_requestor = system.membus.cpu_side_ports
system.cpu.interrupts[0].int_responder = system.membus.mem_side_ports

# Create a DDR3 memory controller and connect it to the membus
system.mem_ctrl = MemCtrl()
system.mem_ctrl.dram = DDR3_1600_8x8()
system.mem_ctrl.dram.range = system.mem_ranges[0]
system.mem_ctrl.port = system.membus.mem_side_ports

# Connect the system up to the membus
system.system_port = system.membus.cpu_side_ports


# Here we set the X86 "hello world" binary. With other ISAs you must specify
# workloads compiled to those ISAs. Other "hello world" binaries for other ISAs
# can be found in "tests/test-progs/hello".
thispath = os.path.dirname(os.path.realpath(__file__))
binary = os.path.join(
thispath,
"../../../",
# "tests/test-progs/hello/bin/x86/linux/test",
)


system.workload = SEWorkload.init_compatible(binary)

# Create a process for a simple "Hello World" application
process = Process()
# Set the command
# cmd is a list which begins with the executable (like argv)
process.cmd = [binary]
# Set the cpu to use the process as its workload and create thread contexts
system.cpu.workload = process
system.cpu.createThreads()

# set up the root SimObject and start the simulation
root = Root(full_system=False, system=system)
# instantiate all of the objects we've created above
m5.instantiate()

print(f"Beginning simulation!")
exit_event = m5.simulate()


EDIT

Problem solved. There were an error on the c code, on the definition of array[size]. Check comment.

Continue reading...