## Line Charts: Performance Comparison of Sorting Algorithms ### Overview The image presents six line charts comparing the average running time (in milliseconds) of three sorting algorithms (WMS, BMS, and RB-Sort) across different numbers of buckets (m). The charts are arranged in a 2x3 grid. The top row shows results for "key-only" sorting, while the bottom row shows results for "key-value" sorting. The columns represent different hardware configurations: Tesla K40c with ECC on, Tesla K40c with ECC off, and GeForce GTX 1080. ### Components/Axes * **Title:** Each chart has a title indicating the type of sorting (key-only or key-value) and the hardware configuration used. * **X-axis:** Number of buckets (m), with values 1, 2, 4, 8, 16, 32, 64, 128, and 256. * **Y-axis:** Average running time (ms), with a scale that varies slightly between charts but generally ranges from 0 to 12 or 0 to 20. * **Legend:** Each chart includes a legend in the top-left corner identifying the three sorting algorithms: * WMS (represented by circles) * BMS (represented by triangles) * RB-Sort (represented by plus signs) ### Detailed Analysis **Chart (a): Key-only: K40c (ECC on)** * **WMS (circles):** Relatively flat, hovering around 3 ms. Values are approximately: (1, 2.8), (2, 3.0), (4, 3.2), (8, 3.3), (16, 3.4), (32, 3.5), (64, 3.6), (128, 3.7), (256, 3.8). * **BMS (triangles):** Starts around 4 ms and increases gradually. Values are approximately: (1, 4.0), (2, 4.2), (4, 4.3), (8, 4.4), (16, 4.5), (32, 5.0), (64, 6.5), (128, 9.5), (256, 12.5). * **RB-Sort (plus signs):** Starts around 6 ms and increases sharply. Values are approximately: (1, 6.0), (2, 6.5), (4, 6.6), (8, 7.0), (16, 7.5), (32, 8.0), (64, 9.0), (128, 11.5), (256, 13.0). **Chart (b): Key-only: K40c (ECC off)** * **WMS (circles):** Relatively flat, hovering around 3 ms. Values are approximately: (1, 3.0), (2, 3.2), (4, 3.3), (8, 3.4), (16, 3.5), (32, 3.6), (64, 3.7), (128, 3.8), (256, 3.9). * **BMS (triangles):** Starts around 4 ms and increases gradually. Values are approximately: (1, 3.8), (2, 4.0), (4, 4.1), (8, 4.2), (16, 4.3), (32, 4.5), (64, 5.2), (128, 7.5), (256, 9.5). * **RB-Sort (plus signs):** Starts around 4 ms and increases sharply. Values are approximately: (1, 4.0), (2, 4.2), (4, 4.4), (8, 4.6), (16, 5.0), (32, 5.5), (64, 6.0), (128, 8.0), (256, 9.5). **Chart (c): Key-only: GTX 1080** * **WMS (circles):** Relatively flat, hovering around 2 ms. Values are approximately: (1, 1.8), (2, 1.9), (4, 2.0), (8, 2.1), (16, 2.2), (32, 2.3), (64, 2.4), (128, 2.5), (256, 2.6). * **BMS (triangles):** Starts around 2 ms and increases gradually. Values are approximately: (1, 1.8), (2, 1.9), (4, 2.0), (8, 2.1), (16, 2.2), (32, 2.4), (64, 3.0), (128, 4.0), (256, 5.0). * **RB-Sort (plus signs):** Starts around 4 ms and increases sharply. Values are approximately: (1, 4.0), (2, 4.1), (4, 4.2), (8, 4.3), (16, 4.4), (32, 4.5), (64, 4.7), (128, 5.2), (256, 7.0). **Chart (d): Key-value: K40c (ECC on)** * **WMS (circles):** Relatively flat, hovering around 6 ms. Values are approximately: (1, 5.8), (2, 6.0), (4, 6.2), (8, 6.3), (16, 6.4), (32, 6.5), (64, 7.0), (128, 7.5), (256, 8.0). * **BMS (triangles):** Starts around 2 ms and increases sharply. Values are approximately: (1, 1.8), (2, 2.0), (4, 2.2), (8, 2.5), (16, 3.0), (32, 4.0), (64, 6.0), (128, 12.0), (256, 18.0). * **RB-Sort (plus signs):** Starts around 12 ms and increases gradually. Values are approximately: (1, 12.5), (2, 13.0), (4, 13.2), (8, 13.5), (16, 14.0), (32, 14.5), (64, 15.5), (128, 17.5), (256, 20.0). **Chart (e): Key-value: K40c (ECC off)** * **WMS (circles):** Relatively flat, hovering around 6 ms. Values are approximately: (1, 5.8), (2, 6.0), (4, 6.2), (8, 6.3), (16, 6.4), (32, 6.5), (64, 7.0), (128, 7.5), (256, 8.0). * **BMS (triangles):** Starts around 2 ms and increases sharply. Values are approximately: (1, 1.8), (2, 2.0), (4, 2.2), (8, 2.5), (16, 3.0), (32, 4.0), (64, 6.0), (128, 10.0), (256, 14.0). * **RB-Sort (plus signs):** Starts around 10 ms and increases gradually. Values are approximately: (1, 10.0), (2, 10.5), (4, 11.0), (8, 11.5), (16, 12.0), (32, 12.5), (64, 13.0), (128, 14.0), (256, 15.0). **Chart (f): Key-value: GTX 1080** * **WMS (circles):** Relatively flat, hovering around 2 ms. Values are approximately: (1, 1.8), (2, 1.9), (4, 2.0), (8, 2.1), (16, 2.2), (32, 2.3), (64, 2.4), (128, 2.5), (256, 2.6). * **BMS (triangles):** Starts around 2 ms and increases gradually. Values are approximately: (1, 1.8), (2, 1.9), (4, 2.0), (8, 2.1), (16, 2.2), (32, 2.4), (64, 3.0), (128, 4.0), (256, 5.5). * **RB-Sort (plus signs):** Starts around 10 ms and increases gradually. Values are approximately: (1, 10.0), (2, 10.1), (4, 10.2), (8, 10.3), (16, 10.4), (32, 10.5), (64, 11.0), (128, 12.0), (256, 14.5). ### Key Observations * **WMS:** The WMS algorithm consistently exhibits the lowest running time and remains relatively stable regardless of the number of buckets. * **BMS:** The BMS algorithm generally has a low running time for a small number of buckets, but the running time increases significantly as the number of buckets increases, especially for key-value sorting. * **RB-Sort:** The RB-Sort algorithm generally has the highest running time, especially for key-value sorting. * **Hardware Impact:** The GTX 1080 generally results in lower running times compared to the K40c, especially for the RB-Sort algorithm. * **ECC Impact:** Turning ECC off on the K40c generally results in slightly lower running times. * **Key-value vs. Key-only:** Key-value sorting generally results in higher running times compared to key-only sorting, especially for the BMS and RB-Sort algorithms. ### Interpretation The data suggests that the WMS algorithm is the most efficient for this particular task, as it consistently exhibits the lowest running time across all hardware configurations and sorting types. The BMS algorithm is efficient for a small number of buckets but becomes less efficient as the number of buckets increases. The RB-Sort algorithm is generally the least efficient. The choice of hardware also has a significant impact on performance. The GTX 1080 generally outperforms the K40c, suggesting that it is better suited for this type of sorting task. Turning ECC off on the K40c can also improve performance, but this may come at the cost of reduced data integrity. The type of sorting (key-only vs. key-value) also affects performance. Key-value sorting generally results in higher running times, suggesting that it is a more complex task.

\n ## Line Charts: Performance Comparison of Sorting Algorithms on Different GPUs ### Overview The image presents six line charts comparing the performance of three sorting algorithms (WMS, BMS, and RB-Sort) on three different GPUs (Tesla K40c with ECC on/off, and GeForce GTX 1080) with varying numbers of buckets. The y-axis represents the average running time in milliseconds (ms), and the x-axis represents the number of buckets, ranging from 1 to 256. Each chart corresponds to a specific GPU and ECC setting. ### Components/Axes * **X-axis Title:** "Number of buckets (m)" * **Y-axis Title:** "Average running time (ms)" * **Legend:** * WMS (represented by circles - 'o') * BMS (represented by triangles pointing upwards - '^') * RB-Sort (represented by plus signs - '+') * **Chart Titles:** * (a) Key-only: K40c (ECC on) * (b) Key-only: K40c (ECC off) * (c) Key-only: GTX 1080 * (d) Key-value: K40c (ECC on) * (e) Key-value: K40c (ECC off) * (f) Key-value: GTX 1080 * **X-axis Markers:** 1, 2, 4, 8, 16, 32, 64, 128, 256 * **Y-axis Scale:** Approximately 0 to 12 ms (charts a & d), 0 to 10 ms (charts b & e), 0 to 15 ms (charts c & f). ### Detailed Analysis or Content Details **Chart (a): Key-only: K40c (ECC on)** * **WMS (o):** Starts at approximately 4.2 ms at 1 bucket, increases steadily to approximately 12.2 ms at 256 buckets. The line slopes upward. * **BMS (^):** Starts at approximately 3.8 ms at 1 bucket, remains relatively flat until 64 buckets (around 4 ms), then increases to approximately 6.5 ms at 256 buckets. * **RB-Sort (+):** Starts at approximately 3.6 ms at 1 bucket, remains relatively flat until 32 buckets (around 3.8 ms), then increases to approximately 5.5 ms at 256 buckets. **Chart (b): Key-only: K40c (ECC off)** * **WMS (o):** Starts at approximately 3.5 ms at 1 bucket, increases steadily to approximately 8.5 ms at 256 buckets. The line slopes upward. * **BMS (^):** Starts at approximately 3.2 ms at 1 bucket, remains relatively flat until 64 buckets (around 3.3 ms), then increases to approximately 5.0 ms at 256 buckets. * **RB-Sort (+):** Starts at approximately 3.1 ms at 1 bucket, remains relatively flat until 32 buckets (around 3.2 ms), then increases to approximately 4.5 ms at 256 buckets. **Chart (c): Key-only: GTX 1080** * **WMS (o):** Starts at approximately 2.0 ms at 1 bucket, increases steadily to approximately 5.5 ms at 256 buckets. The line slopes upward. * **BMS (^):** Starts at approximately 1.8 ms at 1 bucket, remains relatively flat until 64 buckets (around 2.0 ms), then increases to approximately 3.5 ms at 256 buckets. * **RB-Sort (+):** Starts at approximately 1.7 ms at 1 bucket, remains relatively flat until 32 buckets (around 1.8 ms), then increases to approximately 3.0 ms at 256 buckets. **Chart (d): Key-value: K40c (ECC on)** * **WMS (o):** Starts at approximately 7.5 ms at 1 bucket, increases steadily to approximately 12.5 ms at 256 buckets. The line slopes upward. * **BMS (^):** Starts at approximately 6.5 ms at 1 bucket, remains relatively flat until 64 buckets (around 6.7 ms), then increases to approximately 9.5 ms at 256 buckets. * **RB-Sort (+):** Starts at approximately 6.0 ms at 1 bucket, remains relatively flat until 32 buckets (around 6.2 ms), then increases to approximately 8.0 ms at 256 buckets. **Chart (e): Key-value: K40c (ECC off)** * **WMS (o):** Starts at approximately 6.0 ms at 1 bucket, increases steadily to approximately 10.5 ms at 256 buckets. The line slopes upward. * **BMS (^):** Starts at approximately 5.0 ms at 1 bucket, remains relatively flat until 64 buckets (around 5.2 ms), then increases to approximately 8.0 ms at 256 buckets. * **RB-Sort (+):** Starts at approximately 4.5 ms at 1 bucket, remains relatively flat until 32 buckets (around 4.7 ms), then increases to approximately 7.0 ms at 256 buckets. **Chart (f): Key-value: GTX 1080** * **WMS (o):** Starts at approximately 3.5 ms at 1 bucket, increases steadily to approximately 8.0 ms at 256 buckets. The line slopes upward. * **BMS (^):** Starts at approximately 3.0 ms at 1 bucket, remains relatively flat until 64 buckets (around 3.2 ms), then increases to approximately 5.5 ms at 256 buckets. * **RB-Sort (+):** Starts at approximately 2.5 ms at 1 bucket, remains relatively flat until 32 buckets (around 2.7 ms), then increases to approximately 4.5 ms at 256 buckets. ### Key Observations * WMS consistently exhibits the highest running time across all GPUs and settings, especially as the number of buckets increases. * BMS and RB-Sort generally have lower running times than WMS, with RB-Sort often being the fastest. * The GTX 1080 consistently outperforms the Tesla K40c for all algorithms. * Enabling ECC on the K40c generally results in slightly higher running times compared to ECC off. * The performance difference between algorithms is more pronounced with a larger number of buckets. ### Interpretation The data demonstrates the performance characteristics of different sorting algorithms on various GPUs. The GTX 1080 consistently outperforms the K40c, indicating its superior processing capabilities. WMS appears to be the least efficient algorithm, scaling poorly with an increasing number of buckets. BMS and RB-Sort are more efficient, particularly RB-Sort, which maintains lower running times across all scenarios. The slight performance penalty associated with ECC on the K40c suggests a trade-off between performance and data integrity. The "key-value" scenarios generally exhibit higher running times than the "key-only" scenarios, likely due to the additional overhead of handling values alongside keys. These results are valuable for selecting the most appropriate sorting algorithm and hardware configuration based on specific performance requirements and data characteristics. The consistent upward slope of the WMS lines suggests a potential algorithmic complexity issue that becomes more apparent with larger datasets.

## [Line Charts]: Performance Comparison of Sorting Algorithms (WMS, BMS, RB-Sort) ### Overview The image contains six line charts arranged in a 2x3 grid. They compare the average running time (in milliseconds) of three sorting algorithms—WMS, BMS, and RB-Sort—as a function of the number of buckets (m). The comparison is performed across two data types ("key-only" and "key-value") and three hardware/configurations: Tesla K40c with ECC on, Tesla K40c with ECC off, and GeForce GTX 1080. ### Components/Axes * **Chart Layout:** Six subplots labeled (a) through (f). * **X-Axis (All Charts):** "Number of buckets (m)". The scale is logarithmic, with major tick marks at 1, 2, 4, 8, 16, 32, 64, 128, and 256. * **Y-Axis (All Charts):** "Average running time (ms)". The scale is linear but varies in range per chart. * **Legend (All Charts):** Located in the top-left corner of each subplot. * `WMS`: Red line with circle markers. * `BMS`: Green line with triangle markers. * `RB-Sort`: Blue line with plus sign markers. * **Subplot Titles:** * (a) `key-only: Tesla K40c (ECC on)` * (b) `key-only: Tesla K40c (ECC off)` * (c) `key-only: GeForce GTX 1080` * (d) `key-value: Tesla K40c (ECC on)` * (e) `key-value: Tesla K40c (ECC off)` * (f) `key-value: GeForce GTX 1080` ### Detailed Analysis **Trend Verification & Data Point Extraction (Approximate Values):** **Top Row: Key-Only Data** * **Chart (a) K40c (ECC on):** * **RB-Sort (Blue +):** Starts at ~6 ms (m=1), increases steadily to ~13 ms (m=256). Trend: Consistently highest running time, steep upward slope. * **BMS (Green △):** Starts at ~4 ms (m=1), remains flat until m=16, then increases sharply to ~13 ms (m=256). Trend: Flat then steep rise, converges with RB-Sort at m=256. * **WMS (Red ○):** Starts at ~3 ms (m=1), increases gradually to ~4.5 ms (m=32). Data series ends at m=32. Trend: Lowest running time, gentle upward slope. * **Chart (b) K40c (ECC off):** * **RB-Sort (Blue +):** Starts at ~5 ms (m=1), increases to ~9 ms (m=256). Trend: Highest running time, moderate upward slope. * **BMS (Green △):** Starts at ~4 ms (m=1), increases to ~13 ms (m=256). Trend: Steeper increase than RB-Sort, surpasses it at m=128. * **WMS (Red ○):** Starts at ~2.5 ms (m=1), increases to ~4.5 ms (m=32). Data series ends at m=32. Trend: Lowest running time. * **Chart (c) GTX 1080:** * **RB-Sort (Blue +):** Starts at ~4 ms (m=1), increases to ~7 ms (m=256). Trend: Highest running time, moderate upward slope. * **BMS (Green △):** Starts at ~1.8 ms (m=1), remains flat until m=64, then increases to ~5 ms (m=256). Trend: Flat then sharp rise. * **WMS (Red ○):** Starts at ~1.8 ms (m=1), increases to ~3 ms (m=32). Data series ends at m=32. Trend: Similar to BMS initially, then lower. **Bottom Row: Key-Value Data** * **Chart (d) K40c (ECC on):** * **RB-Sort (Blue +):** Starts at ~12 ms (m=1), increases steeply to ~25 ms (m=256). Trend: Highest running time, very steep upward slope. * **BMS (Green △):** Starts at ~3 ms (m=1), increases to ~18 ms (m=256). Trend: Steep increase, remains below RB-Sort. * **WMS (Red ○):** Starts at ~3 ms (m=1), increases to ~6 ms (m=64). Data series ends at m=64. Trend: Lowest running time. * **Chart (e) K40c (ECC off):** * **RB-Sort (Blue +):** Starts at ~11 ms (m=1), increases to ~18 ms (m=256). Trend: Highest running time. * **BMS (Green △):** Starts at ~4 ms (m=1), increases to ~18 ms (m=256). Trend: Steep increase, converges with RB-Sort at m=256. * **WMS (Red ○):** Starts at ~3 ms (m=1), increases to ~7 ms (m=64). Data series ends at m=64. Trend: Lowest running time. * **Chart (f) GTX 1080:** * **RB-Sort (Blue +):** Starts at ~9 ms (m=1), increases to ~14 ms (m=256). Trend: Highest running time. * **BMS (Green △):** Starts at ~2.5 ms (m=1), remains flat until m=128, then increases to ~6 ms (m=256). Trend: Very flat until a late, sharp rise. * **WMS (Red ○):** Starts at ~2.5 ms (m=1), increases to ~4.5 ms (m=64). Data series ends at m=64. Trend: Lowest running time. ### Key Observations 1. **Algorithm Hierarchy:** Across all configurations, RB-Sort consistently has the highest average running time. WMS consistently has the lowest, followed by BMS. 2. **Scalability:** The running time for all algorithms increases with the number of buckets (m). The rate of increase (slope) is generally steepest for RB-Sort and BMS at higher `m` values, especially for key-value data. 3. **Data Type Impact:** Running times are significantly higher for "key-value" data compared to "key-only" data for the same hardware and algorithm (e.g., compare (a) vs (d)). 4. **Hardware Impact:** The GeForce GTX 1080 generally shows lower running times than the Tesla K40c for the same data type and algorithm (e.g., compare (a) vs (c)). 5. **ECC Impact:** Disabling ECC on the Tesla K40c reduces running times for all algorithms (compare (a) vs (b), (d) vs (e)). 6. **WMS Data Limit:** The WMS algorithm's data series terminates earlier (at m=32 or m=64) than BMS and RB-Sort (which go to m=256) in all charts. ### Interpretation This set of charts provides a performance benchmark for three sorting algorithms under varying conditions. The data suggests that **RB-Sort is the least efficient** of the three in terms of running time, while **WMS is the most efficient**. However, the early termination of the WMS data series might indicate a limitation in its scalability or applicability for a large number of buckets. The **key-value operation is more computationally expensive** than the key-only operation, as expected. The **impact of hardware is clear**, with the consumer-grade GTX 1080 outperforming the professional-grade K40c in these specific tests. Furthermore, **enabling ECC memory on the K40c introduces a measurable performance overhead**, which is a known trade-off for increased reliability. The most notable trend is the **divergent scalability** of the algorithms. BMS and RB-Sort show a non-linear, accelerating increase in running time as `m` grows, particularly for key-value data. In contrast, WMS shows a more linear and gentle increase, though its limited data range prevents a full comparison at high `m`. This suggests WMS may have a better algorithmic complexity class for this specific task, but its practical upper limit on `m` needs investigation. The charts effectively demonstrate the performance trade-offs between algorithm choice, data complexity, hardware selection, and system configuration (ECC).

## Line Charts: GPU Performance Comparison Across Bucket Counts ### Overview The image contains six line charts comparing the average running time (ms) of three sorting algorithms (WMS, BMS, RB-Sort) across different GPU models (Tesla K40c, GeForce GTX 1080) and ECC configurations (on/off). Each chart plots performance against the number of buckets (m), ranging from 1 to 256. ### Components/Axes - **X-axis**: Number of buckets (m) - logarithmic scale (1, 2, 4, 8, 16, 32, 64, 128, 256) - **Y-axis**: Average running time (ms) - linear scale (0-20 ms) - **Legends**: - Red circles (WMS) - Green triangles (BMS) - Blue crosses (RB-Sort) - **Chart Labels**: - Top row: Key-only operations - Bottom row: Key-value operations - GPU/ECC configurations: - Tesla K40c with ECC on - Tesla K40c with ECC off - GeForce GTX 1080 with ECC on - GeForce GTX 1080 with ECC off