e-caste / sdp-q2-project Goto Github PK
View Code? Open in Web Editor NEWA fast C implementation of the GRAIL algorithm for large graphs search. Project Q2 of the System and Device Programming course @ PoliTo
A fast C implementation of the GRAIL algorithm for large graphs search. Project Q2 of the System and Device Programming course @ PoliTo
Since with the current implementation we use arrays, we have to know in advanced how much memory we're going to need for the DAG struct.
Using linked lists (see online for the implementation) we could store the data for each vertex while reading the file, cutting in half the number of file reads required to store the DAG.
This should be done before #3
In order to avoid the "re-creation" of the same threads, we could enlarge the "scanFile" by adding the code of "scanRoot" inside.
SCAN FILE INIT
for(j=0; j < num_threads; j++) {
args[j].filename = argv[1];
args[j].graph = rows;
args[j].total_vertex = num_vertex;
args[j].total_threads = num_threads;
args[j].size_file = size;
args[j].roots_num = &roots_num; // pointer of 'shared' variable
args[j].roots_mutex = roots_mutex; // protection for 'shared' variable
}
printf("Starting the reading of DAG file...\n");
for(i=0; i<num_threads; i++) {
args[i].id = i;
err_code = pthread_create(&threads[i], NULL, scanFile, (void *)&args[i]);
if(err_code) {
printf ("Error number %i in thread %i creation.\n", err_code, i);
exit(1);
}
}
// Wait until all thread end
for(j=0; j < num_threads; j++) {
err_code = pthread_join(threads[j], NULL);
if(err_code) {
printf ("Error number %i in thread %i joining.\n", err_code, j);
exit(1);
}
}
SCAN ROOTS INIT
for(i=0; i<num_threads; i++) {
args[i].id = i;
args[i].roots = roots;
args[i].root_index = &root_index;
err_code = pthread_create(&threads[i], NULL, scanRoots, (void *)&args[i]);
if(err_code) {
printf ("Error number %i in thread %i creation.\n", err_code, i);
exit(1);
}
}
for(j=0; j < num_threads; j++) {
err_code = pthread_join(threads[j], NULL);
if(err_code) {
printf ("Error number %i in thread %i joining.\n", err_code, j);
exit(1);
}
}
NOTE: could be useful barrier for thread syncronization
Sequentially read DAG file and store it in a list of C structures.
Also see if we can reverse engineer dag_stq_gen.c
Some files (at least citPatents.scc.gra
) are corrupted. The correct graph files should be downloaded from https://code.google.com/archive/p/grail/downloads. Replace benchmark.zip
.
This should also be done dynamically in #20
Replace fake_push
with a counter function for the number of roots, protected by a semaphore.
In main
allocate a roots array with the number of counters, then protect the append of a root into the array with a semaphore.
guardare la funzione RandomizedVisitSequentialRecursive
Add launch.sh
to add ability to:
Bash is a prerequisite, but I think the professor will have no problem using it.
In scanRoots
, to prevent pushing data at the exact same moment to the list from different threads.
scrivere una funzione a cui passare tutti i puntatori (labels, ... ) che deallochi tutto:
// Deallocazione di tutte le risorse
for(i=0; i<num_vertex; i++) {
free_list(rows[i].edges_pointer);
pthread_mutex_destroy(rows[i].node_mutex);
free(rows[i].node_mutex);
}
pthread_mutex_destroy(roots_mutex);
free(roots_mutex);
free(roots);
for(i=0; i<num_vertex; i++){
free(labels[i].lbl_start);
free(labels[i].lbl_end);
free(labels[i].visited);
}
free(labels);
free(rows);
free_list_query(head_query);
```
Since we changed unsigned long
to unsigned int
.
As per project specifications, we need to provide memory usage statistics:
See page 2 of Q2 General Project Definition.pdf
. Screenshot here:
Completing #15
Instead of using a constant N for threads, try and detect the number of threads of the physical/virtual machine in which the program is running. E.g. quad-core CPU with hyperthreading -> N=8
This was already mentioned in #3 but deserves its own issue
try to use thread for implement the Index Construction (paper par. 3.1)
REMINDER: Use only one thread for the whole label generation. 1 thread for each label otherwise could be problem in scheduling!
NOTE: We could do better. If we have to generate 4 labels, we create 4 threads. but if our processor support 8 threads, 4 of them do nothing...
Use the number of the system's threads (e.g. CPU has 4 cores 8 threads -> use 8 threads).
We could use the lseek
function to read a buffer of N lines/characters per time per thread.
See docs here
utilizzare almeno i seguenti file con relativi ".h"
lettura DAG
creazione labels
Raggiungibilità Query
See line 4 of RandomizedLabeling
in the paper.
Possible implementation:
for (int i=0; i<roots_len; ++i) {
indexes[i] = i;
}
// TODO implement index randomization
// then do
for (int i=0; i<roots_len; ++i) {
RandomizedVisit(x, roots[indexes[i]], G);
}
This code is already parallelized for d
which is the number of dimensions, or labels, equal to NUM_THREADS.
Currently we are parallelizing the DAG read from file.
We also need to parallelize as much code as possible of the GRAIL algorithm implementation.
Possible approaches:
NUM_THREADS > d
--> (NUM_THREADS - d) threads do nothingvertex_num, roots, etc etc
// TODO: https://en.wikipedia.org/wiki/C_data_types
// Ottimizzazione delle memoria: sostituire int con short se possibile
// Quanti nodi al massimo? unsigned int: [0, 65,535] ; unsigned long int: [0, 4,294,967,295]
Add %*i
to the end of the fscanf
expression.
Example:
NUM_THREADS=4
NUM_QUERIES=1000
-> for each thread, we have 1000/4=250 queries.
Since we are using threads, they all reference the same data structure. Each of them can save in a boolean if each query is reachable or not.
After this, to prevent a lot of semaphore interactions, we wait for all the threads to finish and then we write sequentially, in file2
(.que), at the end of each line, if the query is reachable or not.
Note: remember to write at the end of the output where the results are stored so the professor knows where to look.
for the moment the sequential code works for only 1 label.
try to implement it for multiple labels (In general D < 5)
The problem starts at this line.
When NUM_THREADS
is greater than the number of vertices (in my case, 24 threads vs 10 vertices), the threads will wait indefinitely. This should be fixed by something similar to the following block:
if (NUM_THREADS > num_vertex)
num_threads = num_vertex;
// then use num_threads instead of NUM_THREADS
Tested with citPatents.scc.gra
(download here).
The label for the last node is [0, 0], while in reality it is connected to other nodes.
This is probably because the last vertex/node is always the root node in patents citations.
run.sh
Read the paper to understand this
Tested with v10e3.gra
(working) and v1000000e200.gra
(segfault).
Output of CLion: Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)
In the email Quer said to try with 1,2,3,4 threads. Since we can, we could add some insights for 1,2,8,32 threads.
Keep labels=2 for small DAGs (dense and sparse) and labels=5 for large DAGs.
For the moment the single label is build following the order of the rows (0 to N)
Implement random order in RandomizedVisit() and RandomizedLabeling()
For the moment, just one thread for each label is created. (high level of un-utilized threads)
We could try to create (NUM_THREADS - NUM_LABELS). Each of these will handle inf < ... < sup roots in "random order"
We need to add protection (mutex) to avoid that many thread access the same node cuncurrency.
No parallelization required at this point., see #18 instead.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.