Add script for computing M_i values

Remember, M_i values are the worst-case slowdown of the average-
-case execution time.

Also factor out functions shared with M_ij computation code to a
shared library.

3 files changed, 233 insertions, 145 deletions

diff --git a/smt_analysis/computeLCslowdown.py b/smt_analysis/computeLCslowdown.py
new file mode 100755
index 0000000..bcd22da
--- /dev/null
+++ b/smt_analysis/computeLCslowdown.py
@@ -0,0 +1,73 @@
+#!/usr/bin/python3
+import numpy as np
+import sys
+import plotille.plotille as plt
+from libSMT import *
+TIMING_ERROR = 1000 #ns
+ASYNC_FORMAT = False
+
+def print_usage():
+    print("This program takes in the all-pairs and baseline SMT data and computes the worst-case slowdown against any other task when SMT is enabled.", file=sys.stderr)
+    print("Level-A/B usage: {} <file -A> <file -B> <baseline file>".format(sys.argv[0]), file=sys.stderr)
+    print("Level-C usage: {} <continuous pairs> <baseline file>".format(sys.argv[0]), file=sys.stderr)
+
+# Check that we got the right number of parameters
+if len(sys.argv) < 3:
+    print_usage()
+    exit()
+
+if len(sys.argv) > 3:
+    print("Reading file using synchronous pair format...")
+    print("Are you sure you want to do this? For the RTAS'21 paper, L-A/-B pairs should use the other script.")
+    input("Press enter to continue, Ctrl+C to exit...")
+else:
+    print("Reading file using asynchronous pair format...")
+    ASYNC_FORMAT = True
+
+assert_valid_input_files(sys.argv[1:-1], print_usage)
+
+# Pull in the data
+if not ASYNC_FORMAT:
+    baseline_times, baseline_sample_cnt, baseline_max_times = load_baseline(sys.argv[3])
+    paired_times, paired_offsets, name_to_idx, idx_to_name = load_paired(sys.argv[1], sys.argv[2], len(list(baseline_times.keys())))
+    for key in baseline_times:
+        print(key,max(baseline_times[key]))
+else:
+    baseline_times, baseline_sample_cnt, baseline_max_times = load_baseline(sys.argv[2])
+    paired_times, name_to_idx, idx_to_name = load_fake_paired(sys.argv[1])
+
+# We work iff the baseline was run for the same set of benchmarks as the pairs were
+assert_base_and_pair_keys_match(baseline_times, name_to_idx)
+
+# Only consider benchmarks that are at least an order of magnitude longer than the timing error
+reliableNames = []
+for i in range(0, len(name_to_idx)):
+    benchmark = idx_to_name[i]
+    if min(baseline_times[benchmark]) > TIMING_ERROR * 10:
+        reliableNames.append(benchmark)
+
+# Compute worst-case SMT slowdown for each benchmark
+print("Bench           Mi")
+# Print rows
+sample_f = np.mean # Change this to np.mean to use mean values in Mi generation
+M_vals = []
+for b1 in reliableNames:
+    print("{:<14.14}:".format(b1), end=" ")
+    max_mi = 0
+    # Scan through everyone we ran against and find our maximum slowdown
+    for b2 in reliableNames:
+        time_with_smt = sample_f(paired_times[name_to_idx[b1]][name_to_idx[b2]])
+        time_wout_smt = sample_f(baseline_times[b1])
+        M = time_with_smt / time_wout_smt
+        max_mi = max(max_mi, M)
+    print("{:>10.3}".format(max_mi), end=" ")
+    M_vals.append(max_mi)
+    print("")
+# Print some statistics about the distribution
+print("Average: {:>5.3} with standard deviation {:>5.3} using `{}`".format(np.mean(M_vals), np.std(M_vals), sample_f.__name__))
+Ms = np.asarray(M_vals, dtype=np.float32)
+print(np.sum(Ms <= 1), "of", len(M_vals), "M_i values are at most one -", 100*np.sum(Ms <= 1)/len(M_vals), "percent")
+print(np.sum(Ms > 2), "of", len(M_vals), "M_i values are greater than two -", 100*np.sum(Ms > 2)/len(M_vals), "percent")
+M_vals_to_plot = Ms
+
+print(plt.hist(M_vals_to_plot, bins=10))
diff --git a/smt_analysis/computeSMTslowdown.py b/smt_analysis/computeSMTslowdown.py
index aa7aa21..805def1 100755
--- a/smt_analysis/computeSMTslowdown.py
+++ b/smt_analysis/computeSMTslowdown.py
@@ -3,19 +3,19 @@ from typing import List, Any
 import numpy as np
 from scipy import stats
 import sys
-import os
 import plotille.plotille as plt
 TIMING_ERROR = 1000 #ns
 LEVEL_C_ANALYSIS = False
+from libSMT import *
 
-def print_usage(argv):
+def print_usage():
     print("This program takes in the all-pairs and baseline SMT data and computes how much each program is slowed when SMT in enabled.", file=sys.stderr)
-    print("Level-A/B usage: {} <file -A> <file -B> <baseline file> --cij".format(argv[0]), file=sys.stderr)
-    print("Level-C usage: {} <continuous pairs> <baseline file>".format(argv[0]), file=sys.stderr)
+    print("Level-A/B usage: {} <file -A> <file -B> <baseline file> --cij".format(sys.argv[0]), file=sys.stderr)
+    print("Level-C usage: {} <continuous pairs> <baseline file>".format(sys.argv[0]), file=sys.stderr)
 
 # Check that we got the right number of parameters
 if len(sys.argv) < 3:
-    print_usage(sys.argv)
+    print_usage()
     exit()
 
 if len(sys.argv) > 3:
@@ -24,127 +24,12 @@ else:
     print("Analyzing results using Level-C methodology...")
     LEVEL_C_ANALYSIS = True
 
-# Check that all input files are valid
-for f in sys.argv[1:-1]:
-    if not os.path.exists(f) or os.path.getsize(f) == 0:
-        print("ERROR: File '{}' does not exist or is empty".format(f), file=sys.stderr);
-        print_usage(sys.argv)
-        exit()
+assert_valid_input_files(sys.argv[1:-1], print_usage);
 
 # Print Cij values rather than Mij
 TIMES_ONLY = len(sys.argv) > 4 and "--cij" in sys.argv[4]
 OK_PAIRS_ONLY = len(sys.argv) > 4 and "--cij-ok" in sys.argv[4]
 
-# This parses the result data from unthreaded timing experiments
-# @param f File name to load
-# @returns res Map of benchmark name to sample count
-# @returns samples Map of benchmark name to list of execution time samples
-# @returns max_res May of benchmark to maximum execution time among all samples for that benchmark
-def load_baseline(f):
-    # constants for columns of baseline data files
-    TOTAL_NS = 5
-    BENCH_NAME = 0
-    SAMPLES = 4
-
-    # Load baseline data. This logic is based off the summarize programs
-    res = {} # Map of benchmark to list of all execution time samples
-    samples = {} # Map of benchmark name to sample count
-    max_res = {} # Map of benchmark name to maximum execution time
-
-    with open(f) as fp:
-        for line in fp:
-            s = line.split()
-            if s[BENCH_NAME] not in res:
-                res[s[BENCH_NAME]] = list([int(s[TOTAL_NS])])
-                samples[s[BENCH_NAME]] = int(s[SAMPLES])
-                max_res[s[BENCH_NAME]] = int(s[TOTAL_NS])
-            else:
-                res[s[BENCH_NAME]].append(int(s[TOTAL_NS]))
-                max_res[s[BENCH_NAME]] = max(int(s[TOTAL_NS]), max_res[s[BENCH_NAME]])
-    return res, samples, max_res
-
-# This parses the result data from paired, threaded timing experiements
-# @param file1 The -A file name
-# @param file2 The -B file name
-# @returns time 2D array of benchmark IDs to list of total container execution times
-# @returns offset 2D array of benchmark IDs to list of differences between the start
-#                 of the first and the start of the second benchmark
-# @returns name_to_idx Map of benchmark names to benchmark IDs
-# @returns idx_to_name List which when indexed with benchmark ID will yield the benchmark name
-def load_paired(file1, file2, benchmarkCount):
-    # constants for columns of paired data files
-    FIRST_PROG = 0
-    SECOND_PROG = 1
-    FIRST_CORE = 2
-    SECOND_CORE = 3
-    TRIALS = 4
-    START_S = 5 # Start seconds
-    START_N = 6 # Start nanoseconds
-    END_S = 7   # End seconds
-    END_N = 8   # End nanoseconds
-    RUN_ID = 9
-    JOB_NUM = 10
-
-    with open(file1) as f1:
-        numJobs = int(f1.readline().split()[TRIALS])
-    assert numJobs > 0
-    assert benchmarkCount > 0
-
-    # Total times of each container
-    time=[[[0 for x in range(numJobs)]for y in range(benchmarkCount)]for z in range(benchmarkCount)]
-    # Difference in time between when the first and the second task start in the container
-    offset=[[[0 for x in range(numJobs)]for y in range(benchmarkCount)]for z in range(benchmarkCount)]
-
-    # Some aggregate counters that we update as we go along
-    avg_off = 0
-    avg_off_samp = 0
-
-    # Load paired data
-    bench1 = 0 # Index to what's the current first benchmark being examined
-    bench2 = 0 # Index to what's the current second benchmark being examined
-
-    name_to_idx = {}
-    idx_to_name = [0 for x in range(benchmarkCount)]
-
-    job_idx = 0
-    with open(file1) as f1, open(file2) as f2:
-        for line1, line2 in zip(f1, f2):
-            lineArr1 = line1.split()
-            lineArr2 = line2.split()
-            start1 = int(lineArr1[START_S]) * 10**9 + int(lineArr1[START_N])
-            start2 = int(lineArr2[START_S]) * 10**9 + int(lineArr2[START_N])
-            minStart = min(start1, start2)
-            end1 = int(lineArr1[END_S]) * 10**9 + int(lineArr1[END_N])
-            end2 = int(lineArr2[END_S]) * 10**9 + int(lineArr2[END_N])
-            maxEnd = max(end1, end2)
-            # Time actually co-scheduled is minEnd - maxStart, but Sims uses a different model
-#            time[bench1][bench2][int(lineArr1[JOB_NUM])] = maxEnd - minStart
-            time[bench1][bench2][job_idx] = maxEnd - minStart
-            if lineArr1[SECOND_PROG] == "h264_dec" and lineArr2[JOB_NUM] == 0:
-                print(maxEnd - minStart)
-            # Compute offset: if first job starts at t=0, when does second start?
-#            offset[bench1][bench2][int(lineArr1[JOB_NUM])] = abs(start2-start1)
-            offset[bench1][bench2][job_idx] = abs(start2-start1)
-            # Compute some running statistics
-            avg_off += abs(start2-start1)
-            avg_off_samp += 1
-            # Increment to the next benchmark, this is weird because of the zip()
-            # This is doubly weird because our results are an upper trianguler matrix
-            if job_idx == numJobs - 1: #int(lineArr1[JOB_NUM]) == numJobs - 1:
-                if bench2 < benchmarkCount-1:
-                    bench2 = bench2 + 1
-                    job_idx = 0
-                else:
-                    name_to_idx[lineArr1[FIRST_PROG]] = bench1
-                    idx_to_name[bench1] = lineArr1[FIRST_PROG]
-                    bench1 = bench1 + 1
-                    bench2 = bench1 # bench1 will never again appear as bench2
-                    job_idx = 0
-            else:
-                job_idx += 1
-    print("Average offset is: " + str(avg_off/avg_off_samp) + "ns")
-    return time, offset, name_to_idx, idx_to_name
-
 # Pull in the data
 if not LEVEL_C_ANALYSIS:
     baseline_times, baseline_sample_cnt, baseline_max_times = load_baseline(sys.argv[3])
@@ -152,33 +37,12 @@ if not LEVEL_C_ANALYSIS:
     for key in baseline_times:
         print(key,max(baseline_times[key]))
 else:
-    baseline_times, baseline_sample_cnt, baseline_max_times = load_baseline(sys.argv[2])
     # Paired times use an abuse of the baseline file format
-    paired_times_raw, _, _ = load_baseline(sys.argv[1])
-    benchmarkCount = int(np.sqrt(len(list(paired_times_raw.keys()))))
-    numJobs = len(next(iter(paired_times_raw.values())))
-    paired_times=[[[0 for x in range(numJobs)]for y in range(benchmarkCount)]for z in range(benchmarkCount)]
-    idx_to_name=[]
-    name_to_idx={}
-    bench1 = -1
-    #Generate the indexing approach
-    for pair in sorted(paired_times_raw.keys()):
-        [bench1name, bench2name] = pair.split('+') # Benchmark name is pair concatenated together with a '+' delimiter
-        if bench1 == -1 or bench1name != idx_to_name[-1]:
-            idx_to_name.append(bench1name)
-            name_to_idx[bench1name] = len(idx_to_name) - 1
-            bench1 += 1
-    # Populate the array
-    for bench1 in range(len(idx_to_name)):
-        for bench2 in range(len(idx_to_name)):
-            paired_times[bench1][bench2] = paired_times_raw[idx_to_name[bench1]+"+"+idx_to_name[bench2]]
+    baseline_times, baseline_sample_cnt, baseline_max_times = load_baseline(sys.argv[2])
+    paired_times, name_to_idx, idx_to_name = load_fake_paired(sys.argv[1])
 
 # We work iff the baseline was run for the same set of benchmarks as the pairs were
-if sorted(baseline_times.keys()) != sorted(name_to_idx.keys()):
-    print("ERROR: The baseline and paired experiments were over a different set of benchmarks!", file=sys.stderr)
-    print("Baseline keys:", baseline_times.keys(), file=sys.stderr)
-    print("Paired keys:", name_to_idx.keys(), file=sys.stderr)
-    exit();
+assert_base_and_pair_keys_match(baseline_times, name_to_idx)
 
 # Only consider benchmarks that are at least an order of magnitude longer than the timing error
 reliableNames = []
diff --git a/smt_analysis/libSMT.py b/smt_analysis/libSMT.py
new file mode 100755
index 0000000..cca2fce
--- /dev/null
+++ b/smt_analysis/libSMT.py
@@ -0,0 +1,151 @@
+import numpy as np
+import sys
+import os
+
+def assert_valid_input_files(names, on_fail):
+    # Check that all input files are valid
+    for f in names:
+        if not os.path.exists(f) or os.path.getsize(f) == 0:
+            print("ERROR: File '{}' does not exist or is empty".format(f), file=sys.stderr);
+            on_fail()
+            exit()
+
+# This parses the result data from unthreaded timing experiments
+# @param f File name to load
+# @returns res Map of benchmark name to sample count
+# @returns samples Map of benchmark name to list of execution time samples
+# @returns max_res May of benchmark to maximum execution time among all samples for that benchmark
+def load_baseline(f):
+    # constants for columns of baseline data files
+    TOTAL_NS = 5
+    BENCH_NAME = 0
+    SAMPLES = 4
+
+    # Load baseline data. This logic is based off the summarize programs
+    res = {} # Map of benchmark to list of all execution time samples
+    samples = {} # Map of benchmark name to sample count
+    max_res = {} # Map of benchmark name to maximum execution time
+
+    with open(f) as fp:
+        for line in fp:
+            s = line.split()
+            if s[BENCH_NAME] not in res:
+                res[s[BENCH_NAME]] = list([int(s[TOTAL_NS])])
+                samples[s[BENCH_NAME]] = int(s[SAMPLES])
+                max_res[s[BENCH_NAME]] = int(s[TOTAL_NS])
+            else:
+                res[s[BENCH_NAME]].append(int(s[TOTAL_NS]))
+                max_res[s[BENCH_NAME]] = max(int(s[TOTAL_NS]), max_res[s[BENCH_NAME]])
+    return res, samples, max_res
+
+# This parses the result data from paired, threaded timing experiements
+# @param file1 The -A file name
+# @param file2 The -B file name
+# @returns time 2D array of benchmark IDs to list of total container execution times
+# @returns offset 2D array of benchmark IDs to list of differences between the start
+#                 of the first and the start of the second benchmark
+# @returns name_to_idx Map of benchmark names to benchmark IDs
+# @returns idx_to_name List which when indexed with benchmark ID will yield the benchmark name
+def load_paired(file1, file2, benchmarkCount):
+    # constants for columns of paired data files
+    FIRST_PROG = 0
+    SECOND_PROG = 1
+    FIRST_CORE = 2
+    SECOND_CORE = 3
+    TRIALS = 4
+    START_S = 5 # Start seconds
+    START_N = 6 # Start nanoseconds
+    END_S = 7   # End seconds
+    END_N = 8   # End nanoseconds
+    RUN_ID = 9
+    JOB_NUM = 10
+
+    with open(file1) as f1:
+        numJobs = int(f1.readline().split()[TRIALS])
+    assert numJobs > 0
+    assert benchmarkCount > 0
+
+    # Total times of each container
+    time=[[[0 for x in range(numJobs)]for y in range(benchmarkCount)]for z in range(benchmarkCount)]
+    # Difference in time between when the first and the second task start in the container
+    offset=[[[0 for x in range(numJobs)]for y in range(benchmarkCount)]for z in range(benchmarkCount)]
+
+    # Some aggregate counters that we update as we go along
+    avg_off = 0
+    avg_off_samp = 0
+
+    # Load paired data
+    bench1 = 0 # Index to what's the current first benchmark being examined
+    bench2 = 0 # Index to what's the current second benchmark being examined
+
+    name_to_idx = {}
+    idx_to_name = [0 for x in range(benchmarkCount)]
+
+    job_idx = 0
+    with open(file1) as f1, open(file2) as f2:
+        for line1, line2 in zip(f1, f2):
+            lineArr1 = line1.split()
+            lineArr2 = line2.split()
+            start1 = int(lineArr1[START_S]) * 10**9 + int(lineArr1[START_N])
+            start2 = int(lineArr2[START_S]) * 10**9 + int(lineArr2[START_N])
+            minStart = min(start1, start2)
+            end1 = int(lineArr1[END_S]) * 10**9 + int(lineArr1[END_N])
+            end2 = int(lineArr2[END_S]) * 10**9 + int(lineArr2[END_N])
+            maxEnd = max(end1, end2)
+            # Time actually co-scheduled is minEnd - maxStart, but Sims uses a different model
+#            time[bench1][bench2][int(lineArr1[JOB_NUM])] = maxEnd - minStart
+            time[bench1][bench2][job_idx] = maxEnd - minStart
+            if lineArr1[SECOND_PROG] == "h264_dec" and lineArr2[JOB_NUM] == 0:
+                print(maxEnd - minStart)
+            # Compute offset: if first job starts at t=0, when does second start?
+#            offset[bench1][bench2][int(lineArr1[JOB_NUM])] = abs(start2-start1)
+            offset[bench1][bench2][job_idx] = abs(start2-start1)
+            # Compute some running statistics
+            avg_off += abs(start2-start1)
+            avg_off_samp += 1
+            # Increment to the next benchmark, this is weird because of the zip()
+            # This is doubly weird because our results are an upper trianguler matrix
+            if job_idx == numJobs - 1: #int(lineArr1[JOB_NUM]) == numJobs - 1:
+                if bench2 < benchmarkCount-1:
+                    bench2 = bench2 + 1
+                    job_idx = 0
+                else:
+                    name_to_idx[lineArr1[FIRST_PROG]] = bench1
+                    idx_to_name[bench1] = lineArr1[FIRST_PROG]
+                    bench1 = bench1 + 1
+                    bench2 = bench1 # bench1 will never again appear as bench2
+                    job_idx = 0
+            else:
+                job_idx += 1
+    print("Average offset is: " + str(avg_off/avg_off_samp) + "ns")
+    return time, offset, name_to_idx, idx_to_name
+
+# Paired times use an abuse of the baseline file format
+def load_fake_paired(fake_paired_filename):
+    paired_times_raw, _, _ = load_baseline(fake_paired_filename)
+    benchmarkCount = int(np.sqrt(len(list(paired_times_raw.keys()))))
+    numJobs = len(next(iter(paired_times_raw.values())))
+    paired_times=[[[0 for x in range(numJobs)]for y in range(benchmarkCount)]for z in range(benchmarkCount)]
+    idx_to_name=[]
+    name_to_idx={}
+    bench1 = -1
+    #Generate the indexing approach
+    for pair in sorted(paired_times_raw.keys()):
+        [bench1name, bench2name] = pair.split('+') # Benchmark name is pair concatenated together with a '+' delimiter
+        if bench1 == -1 or bench1name != idx_to_name[-1]:
+            idx_to_name.append(bench1name)
+            name_to_idx[bench1name] = len(idx_to_name) - 1
+            bench1 += 1
+    # Populate the array
+    for bench1 in range(len(idx_to_name)):
+        for bench2 in range(len(idx_to_name)):
+            paired_times[bench1][bench2] = paired_times_raw[idx_to_name[bench1]+"+"+idx_to_name[bench2]]
+    return paired_times, name_to_idx, idx_to_name
+
+def assert_base_and_pair_keys_match(baseline_times, name_to_idx):
+    if sorted(baseline_times.keys()) != sorted(name_to_idx.keys()):
+        print("ERROR: The baseline and paired experiments were over a different set of benchmarks!", file=sys.stderr)
+        print("Baseline keys:", baseline_times.keys(), file=sys.stderr)
+        print("Paired keys:", name_to_idx.keys(), file=sys.stderr)
+        exit();
+