IMSuite Kernel Categorization
IMSuite implements twelve classical distributed algorithms as
benchmark kernels.
Considering the different popular parallel programming styles,
IMSuite consists multiple variations for each kernel in two task parallel
languages
(
X10 and
HJ).
These variations can be categorized under following two heads:
- Varying Synchronization Primitives - with and without fine grain synchronization primitives.
- Varying Forms of Parallelization - data parallel and recursive task parallel.
IMSuite Packaging
The IMSuite tar file consists of kernels subdivided under
two heads -
timing and
characterization.
The main intuition for this approach is summarized through
following points:
Timing
- These kernels are specifically designed to measure the time taken by a
benchmark kernel to execute.
- Each kernel part of this category provides a measure of the time taken in
nanoseconds.
- The timing phase does not include time taken to initialize the data
structures, print and validate the output.
Characterization
- These kernels measure the properties relevant to the distributed and
parallel systems.
- We provide counters for measuring the total amount of dynamic communication
and atomic/isolated operations.
- We also provide counters to calculate the communication per round.
- For the recursive kernels we provide counters for calculating dynamic async,
finish and synchronization operations in addition to the other counters.
The kernels are further subdivided under following four language subsets:
- X10-FA - utilizes X10 constructs finish, async and atomic for task
creation, join and mutual exclusion respectively.
Here synchronization is achieved by joining/terminating the tasks and
recreating them later.
- X10-FAC - utilizes the abstraction of clocks in addition to the
constructs of X10-FA.
- HJ-FA - utilizes HJ constructs finish, async and atomic for task
creation, join and mutual exclusion respectively.
- HJ-FAP - utilizes the abstraction of phasers in addition to the
constructs of HJ-FA.
Benchmark Details
IMSuite consists of twelve classical algorithms covering important and complex problems in
the domain of distributed systems such as breadth first search, consensus,
routing table creation, dominating set, maximal independent set, committee
creation, leader election, spanning tree and vertex coloring.
A brief discussion on these classical algorithms follows:
- Breadth First Search: We use two different breadth first search
algorithms.
- Bellman Ford: This algorithm assigns the breadth first
search information in a general network for a given root node.
It outputs the distance of every node from the root.
The time complexity for the algorithm is O(D), where D is the diameter
of the graph.
The algorithm starts by marking the root node and setting its distance
value to 0.
The root node then increments the distance value by one and sends it
to its neighbors.
If a node receives a distance value smaller than its own value,
updation takes place.
- Dijkstra: This algorithm aims to create a breadth
first spanning tree in a general network.
It outputs the BFS tree that marks the parent and child (if any) node
for each node in the network.
The time complexity of this algorithm is O(D^{2}), where D
refers to the diameter of the graph.
But compared to Bellmand Ford algorithm, it has a reduced message
complexity of O(m + n × D).
The algorithm starts by marking the root as the current tree.
In each phase p, nodes at a distance p from the root are added to the
current tree.
Every newly added node echoes its arrival by sending an acknowledgement
to its parent.
Each node receiving an acknowledgement, echoes the acknowledgment back
to its parent.
- Byzantine Agreement: This algorithm aims at generating a consensus
vote among the nodes of a network.
The algorithm admits both " good " and " faulty " nodes.
In each iteration, the good nodes share their vote with their neighbors,
while the faulty ones may send arbitrary votes.
Each node sets its own vote for the next iteration based on the votes
it received in the current iteration.
The time complexity of the algorithm is constant on expectation for complete
graphs, and O(D) otherwise.
- Dijkstra Routing: This algorithm aims to compute a routing table for
each node in the network.
Each node works independently and computes the routing table in parallel.
The routing table contains information such as total cost of the path,
next node on the path to the destination, total hop counts, and so on.
- Dominating Set: This algorithm aims to find a dominating set by
selecting nodes using a probabilistic method that depends on the
neighbors at first and second level of a node.
The algorithm creates a dominating set by coloring the nodes in a specific way:
- Initially color of each node is assumed to be White, i.e. not part
of a dominating set.
- As a node becomes part of the dominating set then its color changes
to Black.
- Color of all the neighbors of a Black node is set to Grey.
- k-Committee: This algorithm partitions the nodes of a network into
committees of size at most k, where k is a given integer.
In the current version of IMSuite we work with static networks.
Initially each node in the network has a key value.
The execution of the algorithm takes place in a set of k phases.
In the initial phase, some of the nodes are designated as
leaders -- the nodes whose key value is the minimum compared to all
their neighbors at a distance ≤ k.
In each subsequent phase, every node that is not associated with any
committee and whose key value is minimum among all its
non-leader neighbors at a distance ≤ k associates itself with a
committee.
- Maximal Independent Set: MIS utilizes a randomized
algorithm to generate a maximal independent set of a set of nodes.
In each iteration each eligible node generates a random number and one or more
nodes get added to the MIS, if their random value is the smallest
among all of their neighbors.
The time complexity of the algorithm is O(log_{2}n) on expectation.
- Leader Election: We implement three popular leader election
algorithms.
In each of these algorithms, every node in the network has
a unique identifier and at the end of the algorithm the node with the highest
identifier is selected as the leader.
- LCR: This algorithm finds the leader for a set of nodes
organized in a ring network, where the data flow is unidirectional.
The distinguishing feature of this algorithm is its simplicity and
negligible computation.
- HS: This algorithm finds the leader from a set of nodes
organized in a ring network, where the data flow is bidirectional.
The algorithm works on the principle, that in each ongoing phase only the leader of the previous phase will be initiator of messages.
- DP: This algorithm finds the leader for a set of nodes
organized in any general network.
We have implemented a synchronous version of the proposed algorithm.
The algorithm computes the leader and the diameter of the network.
- Minimum Spanning Tree: This algorithm generates a minimum spanning
tree of a weighted graph.
The algorithm starts by keeping every node as an independent fragment.
The algorithm proceeds by joining fragments along the minimum weighted edge
till all nodes are in the same fragment.
- Vertex Coloring: This algorithm colors the nodes of a tree with
three colors.
The algorithm starts by initially coloring the nodes of the tree with six
colors which takes O(log^{*}n) time.
Next the algorithm uses a shift down operation (constant time) to color the
tree using three colors.
last modified 11:37, 22 October 2013