Introduction
main.c
main.c
void initializtion(int _size)
result_t，_size
void find_thread(void _argv)
idauthor id，id，。
void find_reprinted_thread(void _argv)
publisher_idbook，bookpublisher_edges
bfs_kth(book_t nodes,size_t count, uint16_t k_lvl)
kbfs，ans
void bfs_shortest(book_t nodes,size_t count, uint16_t b_id2)
bfsidb_id2，ans
void bfs_edge_shortest(book_t nodes,size_t count, uint16_t a_id2)
bfsauther ida_id1edgeauther ida_id2，ansauther ida_id1book
Requirement
COMP2129 Assignment 4
Bookworm
This assessment is CONFIDENTIAL. ©University of Sydney
Assignment Due: 11:59pm Friday, 9 June, 2017
This assessment is worth 10% of the course
Task Description
You are tasked with writing a program that will perform. queries on a graph of books. The books themselves
are represented as an array of book_node_t and will contain categorised edges linking to other books. These
queries will require you to develop a parallelism strategy depending on the query requirements.
Some queries may require simple partitioning of data for each thread to operate on, while others may require
strategy of dynamically partitioning data, checking the distribution of the data and synchronisation in order to
efficiently process and eliminate redundant operations.
You can ask questions on Ed using the assignments category. Please ensure that your work is your own and you
do not share any code or solutions with other students.
Working On Your Assignment
You can work on this assignment using your own computers or the lab machines. Students can also take
advantage of the online code editor on Ed. You will need to navigate to the assessments or workspaces page
where you will be able to run, edit and submit your code from within your browser. However we recommend
you write this code using your own computer or the lab machines.
It is important that you continually back up your assignment files onto your own machine, flash drives, external
hard drives and cloud storage providers. You are encouraged to submit your assignment while you are in the
process of completing it to receive feedback and to check for correctness of your solution.
1
COMP2129 Bookworm
I declare that I have read and understood the University of Sydney Academic Dishonesty and Plagiarism in Coursework Policy, and except where
previously submitted for award or assessment.
I understand that failure to comply with the the Academic Dishonesty and Plagiarism in Coursework Policy, can lead to severe penalties as outlined
under Chapter 8 of the University of Sydney By-Law 1999 (as amended). These penalties may be imposed in cases where any significant portion of my
submitted work has been copied without proper acknowledgement from other sources, including published works, the internet, existing programs, the
work of other students, or work previously submitted for other awards or assessments.
I realise that I may be asked to identify those portions of the work contributed by me and required to demonstrate my knowledge of the relevant material
by answering oral questions or by undertaking supplementary work, either written or in the laboratory, in order to arrive at the final assessment mark.
I acknowledge that the School of Information Technologies, in assessing this assignment, may reproduce it entirely, may provide a copy to another
member of faculty, and or communicate a copy of this assignment to a plagiarism checking service or in house computer program, and that a copy of
the assignment may be maintained by the service or the School of IT for the purpose of future plagiarism checking.
Operating Systems and Machine Principles Page 2 of 10
COMP2129 Bookworm
Structure Details
Your program will be compiled without any optimisations -O0. You are allowed to use compiler intrinsics and
other features for students who would like to take advantage of such features available.
We will provide the graph array but you will need to implement the code required to utilise this data. We will
also specify the number of threads that your query is limited to spawn.
struct book_node_t
struct book_node_t {
uint32_t id;
uint32_t publisher_id;
uint32_t author_id;
uint32_t n_publisher_size;
uint32_t n_author_size;
uint32_t n_cited_books;
uint32_t related_publisher_books;
uint32_t same_author_books;
uint32_t cited_by;
};
The uint32_t elements are indexes referring to other books within the same structure, creating a simple link
between books.
For all queries you will need to return a result_t structure: This structure stores all elements retrieved from the
query and the number of elements. It will be used to determine if your is correct.
struct result_t {
struct book_node_t elements;
size_t n_elements;
};
Each book node will link to other book nodes through one of three of the types of edges (authors, citations,
publishers).
The graph structure (library) itself may contain multiple books of the same id and you cannot assume that a
book is unique from its id alone. However, if a book has the same id and exists multiples times in the graph
you can assume that it has the same citations references and author links.
Operating Systems and Machine Principles Page 3 of 10
COMP2129 Bookworm
Queries
You can think of these similar to SQL select queries on an unindexed table. Some queries are easy to partition
while others may require you to employ a more specific strategy to equally distribute work between threads or
to synchronise threads between others.
The diagrams shown will contain multiple bars, this should not be confused with different arrays, these are
operations that are performed on the same array of data.
Find a book
Searching through the graph to find a specified book.
struct result_t find_book(struct book_node_t nodes,
size_t count, size_t id, uint16_t tcount);
Given an array of nodes and the count, your query will need to find a book by the id given in the function.
Return only one instance of the book.
Find all books by author
Searching through all the books and returning the books that have the same publisher or author.
struct result_t find_all_books_by_author(struct book_node_t nodes,
size_t count, size_t author, uint16_t tcount);
Given an array of nodes and the count, your query will need to return all books that are associated to a publisher
or author.
Operating Systems and Machine Principles Page 4 of 10
COMP2129 Bookworm
Find all books that have been reprinted under another publisher
struct result_t find_all_books_reprinted(struct book_node_t nodes,
size_t count, size_t publisher_id, uint16_t tcount);
Given an array of nodes and the count, your query will need to return all reprinted copies of a book. You may
assume that the publisher_id that is given is the source.
Operating Systems and Machine Principles Page 5 of 10
COMP2129 Bookworm
Find all books that have been reprinted under another publisher
Your query will need to find a specific book (which is included in the result and is also considered level 0).
Your query must only use citation edges and find k degree of separation from book 0.
struct result_t find_all_books_k_distance_from(struct book_node_t nodes,
size_t count, size_t book_id, uint16_t k, uint16_t tcount);
Operating Systems and Machine Principles Page 6 of 10
COMP2129 Bookworm
Find the shortest distance between two books
struct result_t find_shortest_distance_between_books(struct book_node_t nodes,
size_t count, size_t a_id, size_t b_id, uint16_t tcount);
Your query will need to determine the shortest distance between two books. You will need to factor in all edges
from a book node to other book nodes to find the shortest distance. Your query will need return the book nodes
it visits to reach book b from book a inclusive of b and a. In the event that your algorithm finds two or more
shortest paths between a and b of the same length, your algorithm just needs to return one of them.
Operating Systems and Machine Principles Page 7 of 10
COMP2129 Bookworm
Determine the shortest path between any book between author A and B using only a certain edge type
struct result_t find_shortest_edge_type(struct book_node_t nodes,
size_t count, size_t a_id, size_t b_id, uint16_t tcount);
You will need to determine what edge type has the shortest distance for two authors. This requires retrieving
all the books of both authors and determining the shortest distance based on the different edge types. The result
should determine if two authors are closer based on citations or publisher. In the event that your algorithm finds
two or more shortest paths between set a and set b your algorithm just needs to return one of them.
Operating Systems and Machine Principles Page 8 of 10
COMP2129 Bookworm
Algorithms
You may implement each of these algorithms depending on what query you want it used for.
Breadth First Search
Breadth first search will check its neighbours before moving onto its neighbour’s neighbours and so on.
BFS(G, v)
Queue q;
for all vertices u in G
u.seen = false
q.enqueue(v)
while(!q.empty())
u = q.dequeue()
if u.seen is false
u.seen = true
for all neighbours w of u
q.enqueue(w)
Depth First Search
Depth first search starts at some vertex in the graph and traverses the graph as far as it can before backtracking
and traversing neighbours of that node.
DFS(G, v)
Stack s;
for all vertices u in G
u.seen = false
s.push(v)
while(!s.empty())
u = s.pop()
if u.seen is false
u.seen = true
for all neighbours w of u
s.push(w)
You may apply a Breadth First Search or Depth First Search depending on what you are familiar with or what
you think is appropriate. You are also free to implement something different if it fits your need.
Operating Systems and Machine Principles Page 9 of 10
COMP2129 Bookworm
Testing and Submission Details
You will be provided with simple benchmarking code for this assessment called worm_bench and its source.
It will time your query as well as load any expected results you have stored. Your program must produce no
errors on the lab machines and Ed and will be compiled with the command:
clang -O0 -std=gnu11 -march=native -lm -lpthread
You are to submit your assessment using Ed which will check for correctness of your queries. In the event that
your program does not produce the correct output your program will not checked for performance.
Marking
3 Marks assignment for the correctness of your program. This requires implementing all queries specified in
the assignment and ensuring that they will return the correct result.
5 Marks are assigned based on the performance of your code related to the benchmark. This is tested on
a separate machine. Submissions that are faster or equal to the benchmark set, you will receive full marks.
Submissions faster than a basic implementation will receive a minimum of 2.5 marks.
2 Marks are assigned for a manual marking component in your tutorial. This will be based on your submission
prior to the 5th of June 2017 10:00am AEST.
This manual marking component will assess your current progress of your assessment, styling (indentation and
function layout) and also explaining your code to your tutor.
Warning: Any attempts to deceive or disrupt the marking system will result in an immediate zero for the entire
assignment. Negative marks can be assigned if you do not properly follow the assignment specification, or your
code is unnecessarily or deliberately obfuscated.
Operating Systems and Machine Principles Page 10 of 10