-
Notifications
You must be signed in to change notification settings - Fork 0
c. Examples
János Czentye edited this page Aug 3, 2023
·
1 revision
Validation results of a subset of our algorithms with a fully-serialized block execution model, which are executed with our validation script using different configurations and a random-generated input call graph of size 10.
Used algorithmic parameters (if applicable):
- Root node ID (root): 1
- Memory limit (M): 6
- Available vCPU count (N): 1
- Critical path's end node ID (cp_end): 10
- Latency limit: (L): 500
- Platform delay: (delay): 10
- Bidirectional elimination (bidirectional): True
- Cost approximation ratio (Epsilon): 0.0
- Latency violation ratio (Lambda): 0.0
Exact algorithms are configured to yield all optimal solutions (if exists) with the numerating
format {alg}_{num}.
Execution results:
| Algorithm | Partitioning | Cost | Latency | Time (s) |
|---|---|---|---|---|
| GREEDY_0 | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.0237468 |
| GREEDY_1 | [[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]] |
858 | 474 | 0.0237468 |
| GREEDY_2 | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.0237468 |
| GREEDY_ILP_0 | [[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]] |
858 | 474 | 0.0994363 |
| GREEDY_ILP_1 | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.0994363 |
| GREEDY_ILP_2 | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.0994363 |
| GREEDY_PAR_0 | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.038427 |
| GREEDY_PAR_1 | [[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]] |
858 | 474 | 0.038427 |
| GREEDY_PAR_2 | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.038427 |
| GREEDY_ILP_PAR_0 | [[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]] |
858 | 474 | 0.102994 |
| GREEDY_ILP_PAR_1 | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.102994 |
| GREEDY_ILP_PAR_2 | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.102994 |
| ILP_CFG_HYBRID | [[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]] |
858 | 474 | 0.0165484 |
| ILP_CFG_GREEDY | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.0149026 |
| ILP_CFG_HYBRID_PAR | [[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]] |
858 | 474 | 0.0171261 |
| ILP_CFG_GREEDY_PAR | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.0205383 |
| ILP_MTX | [[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]] |
858 | 474 | 0.0256266 |
| ILP_MTX_PAR | [[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]] |
858 | 474 | 0.021875 |
| PSEUDO_B | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.00099376 |
| PSEUDO_B_MP | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.0173008 |
| PSEUDO_B_PAR | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.00185842 |
| PSEUDO_L | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.00180759 |
| PSEUDO_L_MP | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.0121728 |
| PSEUDO_L_PAR | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.00089129 |
| PSEUDO_L_PAR_MP | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.0101648 |
| BIHEUR_B | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.00098761 |
| BIFPTAS_L | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.00141839 |
| BIFPTAS_L_DUAL | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 471 | 0.00127962 |
| CHAIN_DECOMP | [[1, 3, 4, 5], [2], [6, 9], [7], [8, 10]] |
882 | 433 | 0.00018376 |
| TREE_CLUSTER | [[1, 2, 3], [4], [5], [6, 7, 8, 9, 10]] |
888 | 455 | 0.00242717 |
| MINW_UNBOUDED | [[1, 3, 4, 5], [2], [6, 7, 8, 9], [10]] |
858 | 0.000227 | |
| MINW_HEUR | [[1, 2, 3], [4, 5, 6, 8, 9, 10], [7]] |
858 | 443 | 0.00051312 |
| CSP | [[1, 3, 4, 5], [2], [6, 9], [7], [8, 10]] |
882 | 433 | 0.0174952 |
| GREEDY_CHAIN_PART_0 | [[1, 3, 4, 6, 9], [2], [5], [7], [8, 10]] |
1200 | 357 | 0.00852332 |
| GREEDY_CHAIN_PART_1 | [[1, 2], [3, 4, 6, 9], [5], [7], [8, 10]] |
1200 | 367 | 0.00852332 |
| GREEDY_CHAIN_PART_2 | [[1, 2], [3, 4, 6, 8, 10], [5], [7], [9]] |
1200 | 357 | 0.00852332 |
| GREEDY_CHAIN_PART_3 | [[1, 2], [3, 4, 5], [6, 9], [7], [8, 10]] |
1200 | 377 | 0.00852332 |
| GREEDY_CHAIN_PART_4 | [[1, 2], [3, 4, 5], [6, 8, 10], [7], [9]] |
1200 | 367 | 0.00852332 |
| CHAIN_META_PART | [[1, 2], [3, 4, 6, 8, 10], [5], [7], [9]] |
1200 | 1 | 0.00143348 |
| CHAIN_MIN_PART | [[1, 3, 4, 6, 9], [2], [5], [7], [8, 10]] |
1200 | 1 | 0.00027455 |
| CHAIN_SEQ_PART | [[1, 3, 4, 6, 9], [2], [5], [7], [8, 10]] |
1200 | 1 | 0.00040146 |
| CHAIN_PART | [[1, 3], [2], [4, 6], [5], [7], [8], [9], [10]] |
1064 | 428 | 0.00031237 |
| CHAIN_PART_SER | [[1, 3], [2], [4, 6], [5], [7], [8], [9], [10]] |
1064 | 428 | 0.00040676 |
| GREEDY_GEN_ILP_0 | [([1, 3, 4, 5], F[6,1,1.0]), ([2], F[6,1,1.0]), ([6, 8, 9, 10], F[6,1,1.0]), ([7], F[6,1,1.0])] |
858 | 474 | 0.096224 |
| GREEDY_GEN_ILP_1 | [([1, 3, 4, 5], F[6,1,1.0]), ([2], F[6,1,1.0]), ([6, 7, 8, 9], F[6,1,1.0]), ([10], F[6,1,1.0])] |
858 | 471 | 0.096224 |
| GREEDY_GEN_ILP_2 | [([1, 2, 3], F[6,1,1.0]), ([4, 5, 6, 8, 9, 10], F[6,1,1.0]), ([7], F[6,1,1.0])] |
858 | 443 | 0.096224 |
| GEN_ILP_CFG | [([1, 2, 3], F[6,1,1.0]), ([4, 5, 6, 8, 9, 10], F[6,1,1.0]), ([7], F[6,1,1.0])] |
858 | 443 | 0.0153992 |
| GEN_ILP_MTX | [([1, 3, 4, 5], F[6,1,1.0]), ([2], F[6,1,1.0]), ([6, 8, 9, 10], F[6,1,1.0]), ([7], F[6,1,1.0])] |
858 | 474 | 0.0236516 |
| BASELINE_NO_PART | [[1], [2], [3], [4], [5], [6], [7], [8], [9], [10]] |
1090 | 472 | 0.00022843 |
| BASELINE_SINGLE | [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]] |
822 | 686 | 0.00013826 |
| GREEDY_CPATH_CHAIN_0 | [[0], [1, 2, 3, 4, 5]] |
400 | 357 | 0.00108808 |
| CPATH_CHAIN_MIN | [[0], [1, 2, 3, 4, 5]] |
400 | 357 | 0.00027672 |
| CPATH_CHAIN | [[0], [1, 2, 3, 4, 5]] |
400 | 357 | 0.00031096 |
| CPATH_CHAIN_VEC | [[0], [1, 2, 3, 4, 5]] |
400 | 357 | 0.00079894 |
| GREEDY_CPATH_SER_CHAIN_0 | [[0, 1, 2], [3, 4, 5]] |
553 | 474 | 0.00102678 |
| CPATH_SER_CFG_ILP | [[0, 1, 2], [3, 4, 5]] |
553 | 474 | 0.00866781 |
| CPATH_SER_MTX_ILP | [[0, 1, 2], [3, 4, 5]] |
553 | 474 | 0.0115294 |
Tests are conducted on Ubuntu 5.15.0-69-generic with AMD EPYC-Rome Processor @ 2.35GHz.