Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 8884fd4

Browse filesBrowse files
ClaireggggClaireClaireClaire1a1a11a
authored
Integrate Appr MRC Algos (#143)
* a small fix in trace detection * mini changed * SHARDS & Mini Checked * Write Readme.md * Scripts updated, bug fixed * readme updated * readme updated * test passed * test added * test updated --------- Co-authored-by: Claire <Claire@node0.claire-244061.fast25-ae-pg0.utah.cloudlab.us> Co-authored-by: Claire <Claire@node0.claire-244435.fast25-ae-pg0.utah.cloudlab.us> Co-authored-by: Claire <Claire@node0.claire-244458.fast25-ae-pg0.utah.cloudlab.us> Co-authored-by: Juncheng Yang <1a1a11a@users.noreply.github.com>
1 parent 2cf9d2d commit 8884fd4
Copy full SHA for 8884fd4

File tree

Expand file treeCollapse file tree

20 files changed

+2105
-5
lines changed
Filter options
Expand file treeCollapse file tree

20 files changed

+2105
-5
lines changed

‎README.md

Copy file name to clipboardExpand all lines: README.md
+6Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -178,6 +178,12 @@ python3 plot_mrc_size.py --tracepath ../data/twitter_cluster52.csv --trace-forma
178178

179179
# plot miss ratio over time
180180
python3 plot_mrc_time.py --tracepath ../data/twitter_cluster52.csv --trace-format csv --trace-format-params="time-col=1, obj-id-col=2, obj-size-col=3, delimiter=,," --algos=fifo,lru,lecar,s3fifo --report-interval=30 --miss-ratio-type="accu"
181+
182+
# plot miss ratio over size using SHARDS
183+
python3 plot_appr_mrc.py SHARDS ../data/twitter_cluster52.vscsi vscsi 0.01
184+
185+
# plot miss ratio over size using Miniature Simulations
186+
python3 plot_appr_mrc.py MINI ../data/twitter_cluster52.vscsi vscsi s3fifo "0.0001,0.0002,0.0004,0.0008,0.001,0.002,0.004,0.008,0.01,0.02,0.04,0.08,0.1,0.2,0.4,0.8" 0.001,0.01,0.1,1 --extra_args "--ignore-obj-size 1"
181187
```
182188

183189
---

‎libCacheSim/bin/CMakeLists.txt

Copy file name to clipboardExpand all lines: libCacheSim/bin/CMakeLists.txt
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11

22

3-
3+
add_subdirectory(MRC)
44
add_subdirectory(cachesim)
55
# add_subdirectory(traceWriter)
66
add_subdirectory(distUtil)

‎libCacheSim/bin/MRC/CMakeLists.txt

Copy file name to clipboard
+5Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
2+
add_executable(MRC main.c parser_shard.c SHARDS.c ../cli_reader_utils.c ../../dataStructure/histogram.c ../../dataStructure/splay_tuple.c ../../dataStructure/splay.c parser_mini.c Miniatures.c)
3+
target_link_libraries(MRC ${ALL_MODULES} ${LIBS} ${CMAKE_THREAD_LIBS_INIT} utils)
4+
install(TARGETS MRC RUNTIME DESTINATION bin)
5+

‎libCacheSim/bin/MRC/Miniatures.c

Copy file name to clipboard
+24Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
#include <math.h>
2+
3+
#include "../../cache/cacheUtils.h"
4+
#include "../../include/libCacheSim/evictionAlgo.h"
5+
#include "../../include/libCacheSim/plugin.h"
6+
#include "../../include/libCacheSim/simulator.h"
7+
#include "../../profiler/simulator.c"
8+
#include "../../utils/include/myprint.h"
9+
#include "../../utils/include/mystr.h"
10+
#include "mrc_internal.h"
11+
12+
cache_stat_t *generate_mini_mrc(struct MINI_arguments *args) {
13+
reader_t **readers = my_malloc_n(reader_t *, args->n_cache_size * args->n_eviction_algo);
14+
for (int i = 0; i < args->n_cache_size * args->n_eviction_algo; i++) {
15+
if (args->cache_size_ratio[i] == 0) {
16+
args->cache_size_ratio[i] = args->cache_size_ratio[0];
17+
}
18+
args->reader->init_params.sampler = create_SHARDS_sampler(args->cache_size_ratio[i]);
19+
readers[i] = clone_reader(args->reader);
20+
}
21+
cache_stat_t *result = simulate_with_multi_caches_scaling(readers, args->caches, args->n_cache_size * args->n_eviction_algo,
22+
NULL, 0, args->warmup_sec, args->n_thread, true);
23+
return result;
24+
}

‎libCacheSim/bin/MRC/SHARDS.c

Copy file name to clipboard
+132Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
#include <stdio.h>
2+
#include <stdlib.h>
3+
#include <time.h>
4+
5+
#include "../../dataStructure/histogram.h"
6+
#include "../../dataStructure/splay.h"
7+
#include "../../dataStructure/splay_tuple.h" ///users/Claire/libCacheSim/libCacheSim/profiler/dist.c
8+
#include "../../include/libCacheSim/reader.h"
9+
#include "../../include/libCacheSim/sampling.h"
10+
#include "../../profiler/dist.c" // for get_stack_dist_add_req, etc.
11+
#include "../../utils/include/mymath.h"
12+
#include "../../utils/include/mystr.h"
13+
#include "../../utils/include/mysys.h"
14+
#include "mrc_internal.h"
15+
16+
#ifdef __cplusplus
17+
extern "C" {
18+
#endif
19+
20+
uint64_t simulate_shards_mrc(struct PARAM *params);
21+
22+
// Compute reuse distance for each request in fixed-rate mode.
23+
int64_t compute_distance_fixed_rate(struct PARAM *params, request_t *req, uint64_t timestamp) {
24+
int64_t last_access = -1;
25+
int64_t distance =
26+
get_stack_dist_add_req(req, &params->distance_tree, params->lookup_hash, (int64_t)timestamp, &last_access);
27+
return distance;
28+
}
29+
30+
// Compute reuse distance for each request in fixed-size mode.
31+
int64_t compute_distance_fixed_size(struct PARAM *params, request_t *req, uint64_t timestamp) {
32+
int64_t last_access = -1;
33+
int64_t distance =
34+
get_stack_dist_add_req(req, &params->distance_tree, params->lookup_hash, (int64_t)timestamp, &last_access);
35+
36+
// If the object has not been accessed before, insert it into the priority tree.
37+
if (distance == -1) {
38+
struct key *new_tuple = malloc(sizeof(struct key));
39+
new_tuple->L = req->obj_id;
40+
new_tuple->Tmax = (req->hv) & ((1 << 24) - 1);
41+
params->prio_tree = insert_t(new_tuple, params->prio_tree);
42+
}
43+
44+
// Update the priority tree and lookup hash when number of stored objects exceeds the threshold.
45+
while (params->prio_tree != NULL && params->prio_tree->value >= params->threshold) {
46+
struct key *max = find_max_t(params->prio_tree)->key;
47+
uint64_t last_max = 0;
48+
params->rate = (double)max->Tmax / (double)(1 << 24);
49+
//printf("rate: %f\n", params->rate);
50+
// Update the sampler ratio when stored object overflows
51+
params->reader->sampler->sampling_ratio = params->rate;
52+
while ((last_max == max->Tmax) || (last_max == 0)) {
53+
obj_id_t id = max->L;
54+
if (id==req->obj_id) distance = -2;
55+
last_max = max->Tmax;
56+
// Remove the key from prio_tree and update lookup and distance_tree.
57+
params->prio_tree = splay_delete_t(max, params->prio_tree);
58+
gpointer hash_value_inner = g_hash_table_lookup(params->lookup_hash, GSIZE_TO_POINTER((gsize)id));
59+
g_hash_table_remove(params->lookup_hash, GSIZE_TO_POINTER((gsize)id));
60+
params->distance_tree = splay_delete((long long)hash_value_inner, params->distance_tree);
61+
if (params->prio_tree)
62+
max = find_max_t(params->prio_tree)->key;
63+
else
64+
break;
65+
}
66+
}
67+
68+
return distance;
69+
}
70+
71+
uint64_t simulate_shards_mrc(struct PARAM *params) {
72+
reader_t *reader = params->reader;
73+
request_t *req = new_request();
74+
uint64_t timestamp = 0;
75+
uint64_t n_req=0;
76+
read_one_req(reader, req);
77+
while (req->valid) {
78+
int64_t distance = params->compute_distance(params, req, timestamp);
79+
if (distance == -2) {
80+
read_one_req(reader, req);
81+
timestamp++;
82+
n_req++;
83+
continue;
84+
}
85+
update_histogram(params->data, distance, params->rate);
86+
read_one_req(reader, req);
87+
timestamp++;
88+
n_req++;
89+
}
90+
free_request(req);
91+
return n_req;
92+
}
93+
94+
void generate_shards_mrc(struct PARAM *params, char *path) {
95+
srand(time(NULL));
96+
set_rand_seed(rand());
97+
98+
// Calculate the number of requests in the original trace.
99+
params->reader->init_params.sampler->sampling_ratio = 1.0;
100+
params->reader->sampler->sampling_ratio = 1.0;
101+
uint64_t n_req = get_num_of_req(params->reader);
102+
printf("n_req: %lu\n", n_req);
103+
params->reader->init_params.sampler->sampling_ratio = params->rate;
104+
params->reader->sampler->sampling_ratio = params->rate;
105+
106+
// Initialize the data structures.
107+
params->data = init_histogram();
108+
params->prio_tree = NULL;
109+
params->distance_tree = NULL;
110+
params->lookup_hash = g_hash_table_new(g_direct_hash, g_direct_equal);
111+
112+
// Start the simulation.
113+
uint64_t read_req=simulate_shards_mrc(params);
114+
115+
// In fixed-size mode, perform additional post-processing.
116+
if (params->ver == true) {
117+
wrap_up_histogram(params->data, params->rate);
118+
}
119+
120+
//SHARDS-adj
121+
adjust_histogram(params->data, n_req, params->rate);
122+
123+
export_histogram_to_csv(params->data, params->rate, path);
124+
g_hash_table_destroy(params->lookup_hash);
125+
free_sTree_t(params->prio_tree);
126+
free_sTree(params->distance_tree);
127+
close_reader(params->reader);
128+
}
129+
130+
#ifdef __cplusplus
131+
}
132+
#endif

‎libCacheSim/bin/MRC/main.c

Copy file name to clipboard
+60Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
#ifdef __linux__
2+
#include <sys/sysinfo.h>
3+
#endif
4+
#include <assert.h>
5+
#include <libgen.h>
6+
#include <unistd.h>
7+
#include "../../include/libCacheSim/sampling.h"
8+
#include "../cachesim/internal.h"
9+
#include "mrc_internal.h"
10+
11+
int main(int argc, char **argv) {
12+
if (argc < 5) {
13+
fprintf(stderr, "Usage:\n"
14+
" For SHARDS:\n"
15+
" %s SHARDS <output_file> <trace_file> <trace_type> <rate> [--size SIZE] [other options]\n\n"
16+
" For MINI:\n"
17+
" %s MINI <trace_file> <trace_type> <eviction_algo> <cache_sizes> <rate> <output_file> [other options]\n",
18+
argv[0], argv[0]);
19+
return 1;
20+
}
21+
22+
// printf("Received Arguments:\n");
23+
// for (int i = 0; i < argc; i++) {
24+
// printf("argv[%d]: %s\n", i, argv[i]);
25+
// }
26+
27+
char *algorithm_type = argv[1];
28+
printf("Algorithm type: %s\n", algorithm_type);
29+
if (strcmp(algorithm_type, "MINI") == 0) {
30+
char* path=argv[7];
31+
struct MINI_arguments arguments;
32+
parse_mini_cmd(argc, argv, &arguments);
33+
cache_stat_t *return_value = generate_mini_mrc(&arguments);
34+
35+
FILE *output_file = fopen(path, "w");
36+
if (output_file == NULL) {
37+
perror("Error opening file");
38+
return 1;
39+
}
40+
41+
fprintf(output_file, "Cache Size,Miss Ratio, Miss Ratio Byte\n");
42+
for (int i = 0; i < arguments.n_cache_size * arguments.n_eviction_algo; i++) {
43+
uint64_t cache_size = (uint64_t)((float)return_value[i].cache_size / return_value[i].sampler_ratio);
44+
double miss_ratio = (double)return_value[i].n_miss / (double)return_value[i].n_req;
45+
double miss_ratio_byte = (double)return_value[i].n_miss_byte / (double)return_value[i].n_req_byte;
46+
fprintf(output_file, "%ld,%f, %f\n", cache_size, miss_ratio, miss_ratio_byte);
47+
}
48+
49+
fclose(output_file);
50+
} else if (strcmp(algorithm_type, "SHARDS") == 0) {
51+
struct PARAM params;
52+
char *path = argv[2];
53+
parse_mrc_cmd(argc, argv, &params);
54+
55+
params.mrc_algo(&params, path);
56+
} else {
57+
fprintf(stderr, "Error: unknown algorithm type\n");
58+
return 1;
59+
}
60+
}

‎libCacheSim/bin/MRC/mrc_internal.h

Copy file name to clipboard
+108Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
#pragma once
2+
3+
#include <glib.h>
4+
#include <inttypes.h>
5+
#include <stdbool.h>
6+
#include <stdint.h>
7+
#include "../../dataStructure/histogram.h"
8+
#include "../../dataStructure/splay.h"
9+
#include "../../dataStructure/splay_tuple.h"
10+
#include "../../include/libCacheSim/reader.h"
11+
#include "../../include/libCacheSim/enum.h"
12+
#include "../../include/libCacheSim/cache.h"
13+
#include "../../include/libCacheSim/evictionAlgo.h"
14+
#include "../../include/libCacheSim/reader.h"
15+
#include "../../include/libCacheSim/admissionAlgo.h"
16+
17+
#define N_ARGS 4
18+
#define N_MAX_ALGO 16
19+
#define N_MAX_CACHE_SIZE 128
20+
#define OFILEPATH_LEN 128
21+
22+
// Forward declaration of struct Params
23+
struct PARAM;
24+
25+
26+
#ifdef __cplusplus
27+
extern "C" {
28+
#endif
29+
30+
struct SHARD_arguments {
31+
bool verver;
32+
long size;
33+
float rate;
34+
char* mrc_algo;
35+
char* trace_file;
36+
char *trace_type_str;
37+
trace_type_e trace_type;
38+
char* trace_type_params;
39+
bool ignore_obj_size;
40+
int64_t n_req;
41+
};
42+
43+
struct PARAM {
44+
float rate;
45+
bool ver; // 0 means fixed rate, 1 means fixed size
46+
47+
uint64_t threshold;
48+
//GHashTable* prio_hash;
49+
sTree_tuple* prio_tree; // root of the splay tree
50+
sTree* distance_tree;
51+
ReuseHistogram* data;
52+
GHashTable* lookup_hash;
53+
reader_t *reader;
54+
int64_t (*compute_distance)(struct PARAM *, request_t *, uint64_t);
55+
void (*mrc_algo)(struct PARAM*, char* path);
56+
};
57+
58+
struct MINI_arguments {
59+
/* argument from the user */
60+
char *args[6];
61+
char *trace_path;
62+
char *eviction_algo[N_MAX_ALGO];
63+
int n_eviction_algo;
64+
char *admission_algo;
65+
char *prefetch_algo;
66+
uint64_t cache_sizes[N_MAX_CACHE_SIZE];
67+
float cache_size_ratio[N_MAX_CACHE_SIZE];
68+
int n_cache_size;
69+
int warmup_sec;
70+
71+
char ofilepath[OFILEPATH_LEN];
72+
char *trace_type_str;
73+
trace_type_e trace_type;
74+
char *trace_type_params;
75+
char *eviction_params;
76+
char *admission_params;
77+
char *prefetch_params;
78+
int n_thread;
79+
int64_t n_req; /* number of requests to process */
80+
81+
bool verbose;
82+
int report_interval;
83+
bool ignore_obj_size;
84+
bool consider_obj_metadata;
85+
bool use_ttl;
86+
bool print_head_req;
87+
88+
/* arguments generated */
89+
reader_t *reader;
90+
cache_t *caches[N_MAX_ALGO * N_MAX_CACHE_SIZE];
91+
92+
};
93+
94+
int64_t compute_distance_fixed_rate(struct PARAM *params, request_t *req, uint64_t timestamp);
95+
96+
int64_t compute_distance_fixed_size(struct PARAM *params, request_t *req, uint64_t timestamp);
97+
98+
void generate_shards_mrc(struct PARAM* params, char* path);
99+
100+
cache_stat_t * generate_mini_mrc(struct MINI_arguments* args);
101+
102+
void parse_mrc_cmd(int argc, char **argv, struct PARAM *args);
103+
104+
void parse_mini_cmd(int argc, char* argv[], struct MINI_arguments* args);
105+
106+
#ifdef __cplusplus
107+
}
108+
#endif

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.