=Paper=
{{Paper
|id=Vol-2037/paper43
|storemode=property
|title=Efficient High Performance Computing by User Networks
|pdfUrl=https://ceur-ws.org/Vol-2037/paper_43.pdf
|volume=Vol-2037
|authors=Nunziato Cassavia,Sergio Flesca,Michele Ianni,Elio Masciari,Giuseppe Papuzzo,Chiara Pulice
|dblpUrl=https://dblp.org/rec/conf/sebd/CassaviaFIMPP17
}}
==Efficient High Performance Computing by User Networks==
https://ceur-ws.org/Vol-2037/paper_43.pdf
Efficient High Performance Computing by user
networks
(Extended Abstract)
Nunziato Cassavia2 , Sergio Flesca1 , Michele Ianni1 , Elio Masciari2 , Giuseppe
Papuzzo2 , and Chiara Pulice3
1
DIMES, University of Calabria, Italy
2
ICAR-CNR, Italy
UMIACS, University of Maryland, USA
{flesca,mianni}@dimes.unical.it
{nunziato.cassavia,elio.masciari,giuseppe.papuzzo}@icar.cnr.it
{cpulice}@umiacs.umd.edu
Abstract. The advances in computational techniques both from a software and
hardware viewpoint lead to the development of projects whose complexity could
be quite challenging, e.g., biomedical simulations. In order to deal with the in-
creased demand of computational power many collaborative approaches have
been proposed in order to apply proper partitioning strategy able to assign pieces
of execution to a crowd of workers. In this paper, we address this problem in a
peer to peer way. We leverage the idling computational resources of users con-
nected to a network. More in detail, we designed a framework that allows users
to share their CPU and memory in a secure and efficient way. The latter allows
users help each others by asking the network computational resources when they
face high computing demanding tasks. As we do not require to power additional
resources for solving tasks (we better exploit unused resources already powered
instead), we hypothesize a remarkable side effect at steady state: energy con-
sumption reduction compared with traditional server farm or cloud based execu-
tions.
1 Introduction
Computer Science is a really young discipline whose several branches grew up at im-
pressive rates. Hardware cost is continuously decreasing while its performances are
reaching unprecedented levels. Based on the availability of a plethora of powerful
(portable) computing devices, new computing tasks have been designed and new data
management paradigm emerged (e.g., the well known Big Data metaphore [8, 4, 1, 2]).
Even though the advances in computer sciences lead to quite effective solution im-
plementations, several problems still require too much computational resources for a
single device execution. Indeed, since the introduction of Linux operating system, the
idea of gathering from the crowd the resources for completing a task, have been widely
leveraged.
The word Crowdsourcing was first introduced by Howe [5] in order to define the
process of outsourcing some jobs to the crowd. It is used for a wide group of activities,
as it allows companies to get substantial benefits by solving their problems in effective
and efficient way. Indeed, crowd based solutions have been proposed for a wide range
of applications as in image tagging [6], or sentiment analysis [3] to cite a few.
Many attempts have been made to properly define the very nature of collaborative
distributed systems, however the solution to this apparently trivial task is far from being
easy. As a matter of fact, all the successful systems (e.g., Wikipedia3 , Yahoo! Answers4 ,
Amazon Mechanical Turk5 ) rely on some assumptions: They should be able to involve
project contributors, each contributor should solve a specific task, it is mandatory to ef-
fectively evaluate single contributions, and they should properly react to possible mis-
conduct. The above mentioned points calls for a good trade-off between openness of
the system and quality of service when designing a collaborative environment.
A well known open source framework that is widely used (mainly) for scientific
purposes is BOINC (Berkeley Open Infrastructure for Network Computing)6 . It allows
volunteers to contribute to a wide variety of projects. The computing contribution is
rewarded by credits for getting to a higher rank in a leaderboard. On the opposite side in
recent years a new category of collaborative approaches is born for cryptovalue mining
such as Bitcoin [7]. Users aiming at mining new Bitcoins contribute to a decoding
task and are rewarded with a portion of the gathered money that is proportional to the
effort put in the mining task. Our approach can be seen as a trade-off between BOINC
framework implementation and Bitcoin mining.
More in detail, the novelty of our project is the exploitation of a peer to peer ap-
proach for reusing resources that users do not fully exploit to provide services that are
currently offered by centralized server farm at an high cost with no customization. In
particular, current limitation to high performance computing access (high price and dif-
ficult customization of resources), could be overcome by using our framework. Users
who may need computing power, can simply ask other users that are not fully exploiting
the potential of their computing devices (PC, smartphone, smart TV, etc.).
In order to assess the effectiveness of our solution, we analyzed a typical usage
pattern for the big market of imaging and animation: the rendering of 3D scenes by a
specialized plugin named MozaikoT M 7 . This operation typically engages users com-
puters for several hours. Our experimental analyses evidence that existing solution are
slower than our proposal due to their traditional approach to high performance comput-
ing and more expensive due to high prices of CPU cycles renting. Our plugin provides
high added value to potential customers because it will be faster and cheaper than the
competing solution (further details can be found at www.coremuniti.com).
Our solution do not require the continuous purchase of new servers, as users con-
tinuously provide (up to date) computational power. Finally, the better re-use of already
powered resources could induce a beneficial systemic effect by reducing the overall
3
https://www.wikipedia.org
4
https://answers.yahoo.com/
5
https://www.mturk.com
6
https://boinc.berkeley.edu/
7
We choose this name as Mozaiko is the Esperanto (a universal language) term denoting a
Mosaic that is a good metaphore for our approach that partition a complex task in several
sub-tasks that will be re-assembled like mosaic tiles
energy consumption for complex tasks execution. We plan to further investigate our
conjecture in a future work as we are not able at this stage to generalize our early re-
sults.
Our Contribution. To summarize, we make the following major contributions: 1)
We design and implement a hybrid P2P infrastructure that allows collaboration among
users by sharing unexploited computational resources; 2) We define a robust model for
task partitioning and assignment to network users;
2 Our system in a short
P2P networks features a common goal: the resources of many users and computers can
be used in a collaborative way in order to significantly increase the computing power
available for the users. In “full” P2P networks computers communicate directly each
other thus allowing better bandwidth use. However, there are some inherent drawbacks
to P2P solutions that require some functionalities to be centralized. Those systems can
be used both for data sharing[10] and distributed computation[9], they are denoted as
“hybrid” P2P. Our system, namely Coremuniti, falls in the latter category and aims to
build a P2P network where users can share their unexploited computing resources. In
Fig. 1 we sketched a possible usage scenario for our platform when using Mozaiko
plugin. However, we point out that our platform is general purpose thus can be used for
solving any complex problem that is parallelizable.
Fig. 1. Coremuniti system at work
Users who want to join our network, will download our software that will install the
Coremuniti server on their devices (it is worth noticing that our software is platform
independent). By running the node server, denoted in Fig. 1 as N SA (Node Server
Agent), users can easily set the amount of CPU time they are willing to share with other
users in the network. As they allow task execution, they will be rewarded by credits.
We point out, that our software is executed in parallel with user own activities without
any interaction with them. On the opposite side, users who need additional computing
power to complete specialized tasks (in this paper we present the 3D Rendering case
study) can install the specific software that is denoted in Fig. 1 as N CA that stands
for Node Client Agent (i.e., Mozaiko for the rendering case study). As they start a new
computing intensive task, they simply issue a request to the network for gathering the
required resources. Two cases may occur: 1) they have previously gained (a portion
of) the required credits for running the task (e.g., because they acted as servers) or 2)
they have bought the required credits. In order, to guarantee a high level of service, we
perform the subtask assignment step at the central server. More in detail, to fully take
advantage from the capability of our network, we partition the (possibly huge) task in a
suitable number of (much smaller) subtasks that can be quickly executed by the server
peers.
As subtasks are completed, we check their correctness and reward the participating
peers. In the following, we describe our model for subtask assignment that guarantees
efficient execution for clients and gave to all peers (even if they have limited computing
power) the possibility to be rewarded. Interesting enough, users that are not going to
ask for task execution have the chance to accumulate credits that can be redeemed by
coins or gadgets. As it will be shown in the experimental section, the latter features
makes our framework a more convenient choice w.r.t to other collaborative systems
such as cryptovalue miners. Indeed, in the early stage of development of our system
we performed some preliminary user analysis by asking 500 students at University of
Calabria their interest in joining the network. After specifying our rewarding model all
of them agreed to join the network and they are currently beta testing the software. Due
to space limitation, we will not describe the architecture details and in hat follows we
will describe the most interesting part of our system, i.e. subtask assignment.
3 Subtask Assignment and Credit Rewarding
In this section, we describe our mathematical model for assigning subtask execution
to resource providers whose objective is to minimize the expected completion time
for the overall task. More in detail, as explained above, when a user asks the network
for additional resources, the project s/he is going to execute is partitioned in several
subtasks that can be completed using a limited amount of computational resources by
every node connected to our P2P network . The obtained results are then combined
for producing the project output much as much fast as possible than single machine
execution.
The model assumes the presence of a set of available resource providers RP =
{rp1 , . . . , rpn }, and of a function λc : RP → N × N , that assigns to every resource
provider rp a pair htmin, tmaxi, where tmin (resp. tmax) is the minimum (resp.
maximum) execution time required by the resource node to complete a subtask.
Furthermore, we leverage a credit assignment function which is based on the “use-
fulness” of the result yielded by the resource providers. Specifically, let st be a sub-
task whose execution was assigned c credits and which was assigned to the resource
providers rpi1 , . . . rpix . We order the resource providers rpi1 , . . . rpix ascending w.r.t.
their completion times and store them in a sequence RPst . Resource providers which
did not terminate their subtask are put at the end of the sequence RPst ordered accord-
ing to the percentage of the subtask they completed.
3c
When at least three resource providers completed their work, we assign 10 of the
total credits, paid by the client for running the subtask on the network, to the first three
resource providers in RPst , i.e., the resource providers which “step up on the podium”
c
for returning st result. Moreover, we distribute the remaining 10 credits among the
other resource provider in RPst as follows. For each j ∈ [4..x] we assign to RPst [j]
the credits given by the following formula
c · Compl(RPst [j])
Px ,
10 · k=4 Compl(RPst [k])
where Compl(rp) is the percentage of the subtask st which was completed by rp.
Tasks assignment aims at finding an assignment for resource provider to tasks which
minimize the expected completion time while guaranteeing that:
1. every resource provider is assigned at most a subtask, and
2. every resource provider which is assigned a subtask have the possibility to be
among the first three resource providers completing the subtask.
Subtask assignment proceeds in two phases. First an initial assignment of the vari-
ous subtask to resource is yielded (Algorithm 1). Next, at regular intervals, the systems
checks for the overall completion of the project and assigns resource providers that are
available to new subtasks (Algorithm 2).
Let st be a subtask and RP = {rp1 , . . . , rpk } be the set of resource providers as-
signed to st. The expected completion time of st given RP is denoted as ECst,RP
and is computed as follows. Let t↓ and t↑ be two vectors reporting, respectively,
the minimum and maximum completion times of the resource providers in RP in
increasing order. Let t0 denote the value t↓ [2] and t00 denote the value t↑ [2]. Let
vect = [t0 = t0 , . . . , tk = t00 ] be a vector containing all the values in t↓ and t↑ which
lie in the interval [t0 , t00 ]. Hence, denoting with F 3 (x) the probability that at least three
resource providers complete their job before time limit x, we have that:
R∞ R t00
ECst,RP = 0
(1 − F 3 (x))dx = t0 + t0 (1 − F 3 (x))dx =
0 Pk−1 R ti+1
t + i=0 t (1 − Fi3 (x))dx =
0 Pk−1 i 3
t + i=0 F Fi (ti , ti+1 ),
where Fi3 (x) is the probability that at least three resource providers complete their
work before x time limit given that ti ≤ x ≤ ti+1 and F Fi3 (ti , ti+1 ) is equal to
R ti+1
ti
(1 − Fi3 (x))dx. It is easy to see that F Fi3 (ti , ti+1 ) can be easy derived form the
minum and maximum completion times associated to every resource providers by the
function λc .
Example 1. Consider the case that a set of four resource providers RP = {rp1 , . . . , rp4 }
was assigned to st where λc (rp1 ) = h1, 5i, λc (rp2 ) = h2, 7i, λc (rp3 ) = h6, 7i and
λc (rp4 ) = h4, 8i. In this case, t0 = 4 and t00 = 7 and
EC =
R5 R 6 st,RP R7
4+ 4
(1−F03 (x))dx + 5(1−F13 (x))dx + 6(1−F23 (x))dx =
R5 6
4 + 4(1− x−1 x−2 x−4
)dx + 5(1− x−2 x−4
R
5−17−2 8−4
)dx +
R 7 x−2 x−6 7−2 8−4
x−2 x−6 x−4 x−2 x−6 x−4
1− 7−2 7−6
+ 1 − + 1 − dx =
6
R 5 7−2 x−2 x−4 7−6 8−4
R6 7−2 7−6 8−4
4 + 4(1− x−1 4 5 4
)dx + 5
(1− x−2 x−4
5 4
)dx +
R7 x−2 x−6 x−2 x−6 x−4
x−2 x−6 x−4
6
1− 5 1
+ 5
1 − 1 4
+ 1 − 5 1 4
dx =
h i5 h i6
11x 7x2 7x3 x4 3x 3x2 x3
4 + 10 − 80 + 240 − 320 + 5 + 20 − 60
h 4 i7 5
3 4
+ 10 1
(−126x + 44x2 − 17x 3
+ x4 ) =
6
4 + 901
960
+ 11
15
31
+ 120 ≈ 5.93
The initial subtask assignment is computed by running Algorithm 1. It works in two
phases. First an initial assignment of resource providers to tasks is yielded by assigning
a resource provider at a time to the subtask which minimize the maximum expected
completion time of all the tasks, considering resource providers in ascending order of
their expected completion time (lines 2-8). Next the initial assignment is revised by
swapping pairs of resource providers between tasks. The algorithm iteratively selects
a pair of assignments hst0 , rp0 i, hst00 , rp00 i which once swapped provide the greatest
decrease of the maximum expected completion time (lines 9-12). Finally, the subtask
assignment is returned.
Algorithm 1 Initial Assignment
Input: Resource provider sequence RP of size n
Input: Subtask sequence ST of size k < n3
Output: Tasks assignment SA
1: SA = ∅
2: RP = orderOnExpCompl(RP)
3: for i = 1 to n do
4: st = selectBestFreeST(ST , SA, RP[i])
5: if st 6= null then
6: SA = SA ∪ hst, RP[i]i
7: end if
8: end for
9: repeat
10: (hst0 , rp0 i, hst00 , rp00 i) = selectBestCandidatePair(SA)
11: SA = SA − {hst0 , rp0 i, hst00 , rp00 i} ∪ {hst0 , rp00 i, hst00 , rp0 i}
12: until existsACandidatePair(SA)
13: return SA
Function orderOnExpCompl takes as input a sequence of resource providers RP
and returns RP ordered ascending w.r.t. the expected resource provider completion
time. Function selectBestFreeST returns, given a resource provider rp and a subtask
assignemnt SA, the subtask st ∈ ST such that M axECP (SA∪{hst, rpi}) is the mini-
mum, i.e., st = arg minst∈ST (M axECP (SA∪{hst, rpi})), such that M axECP (SA∪
{hst, rpi}) < M axECP (SA), null otherwise. Since in the initial step of the algo-
rithm it may happen that there is some subtask st in ST such that |SA(st)| = x < 3,
for each subtask st satisfying this constraint, when computing M axECT function se-
lectBestFreeST assumes that 3 − x fake resource providers have been assigned to st,
where the minimum and maximum completion times of these fake resource providers
are max − 1 and max, respectively, where max is a constant value (much) greater than
the maximum completion time of every the resource provider in RP.
Function selectBestCandidatePair returns a pair of assignments hst, rpi and hst0 , rp0 i
in SA such that there not exist assignment hst00 , rp00 i and hst∗ , rp∗ i in SA such that
M axECP (SA−{hst, rpi, hst0 , rp0 i}∪{hst, rp0 i, hst0 , rpi}) > M axECP (SA−{hst00 , rp00 i, hst∗ , rp∗ i}∪
{hst00 , rp∗ i, hst∗ , rp00 i}). Function existsACandidatePair returns true if there is a pair of
assignments hst, rpi and hst0 , rp0 i in SA such that M axECP (SA − {hst, rpi, hst0 , rp0 i} ∪
{hst, rp0 i, hst0 , rpi}) < M axECP (SA). Moreover, both functions selectBestCandidatePair
0 0
and existsACandidatePair consider only pairs of assignments hst, rpi and hst , rp i in
SA such that swapping rp and rp0 guarantees that the probability that rp (resp. rp0 )
is among the first three resource providers assigned to st0 (resp. st) that complete st is
greater than zero.
Our central server runs Algorithm 2 at fixed intervals, in order to check for the
overall completion of the project and assigns resource providers, that have completed
the assigned tasks, to further tasks whose results are not yet available. Before run-
ning this algorithm the system updates the statistics of resource providers which are
assigned to a subtask yielding up to date values for the minimum and maximum com-
pletion times. Essentially Algorithm 2 first orders the available resource providers as-
cending w.r.t. their expected completion times and next iteratively assigns each re-
source provider rp to the subtask st selected by invoking function selectBest. Func-
tion selectBest returns, given a resource provider rp and a subtask assignemnt SA,
the subtask st ∈ ST such that M axECP (SA ∪ hst, rpi) is the minimum, i.e., st =
arg minst∈ST (M axECP (SA∪hst, rpi)), and is such that M axECP (SA∪{hst, rpi}) <
M axECP (SA), null otherwise.
4 Conclusion and Future Work
In this paper, we proposed a hybrid peer to peer architecture for computational resource
sharing. By our network users can provide their unexploited computational resource to
those users who run computational demanding tasks and they are rewarded for their
collaboration. In order to guarantee the efficiency and effectiveness of the computa-
tion process, we design a task partitioning and assignment algorithm that reduce the
execution times while allowing satisfactory revenues for resource providers.
Acknowledgment
The authors thank the Calabria region that fully funded the project development and the
EU commission that awarded our project with a seal of excellence.
Algorithm 2 Incremental Assignment
Input: Available resource providers sequence RP of size n
Input: Subtask sequence ST
Input: Initial Subtasks assignment SA
Input: Subtasks and Resource Providers constraints ST C
Output: Revised Subtasks assignment SA
1: RP = orderOnExpCompl(RP)
2: for i = 1 to n do
3: st = selectBest(ST , SA, RP[i])
4: if st 6= null then
5: SA = SA ∪ hst, RP[i]i
6: end if
7: end for
8: return SA
References
1. D. Agrawal et al. Challenges and opportunities with big data. A community white paper
developed by leading researchers across the United States. 2012.
2. V. R. Borkar, M. J. Carey, and C. Li. Inside “Big Data Management”: Ogres, Onions, or
Parfaits? In International Conference on Extending Database Technology, pages 3–14, 2012.
3. A. Brew, D. Greene, and P. Cunningham. Using crowdsourcing and active learning to track
sentiment in online media. In Proceedings of the 2010 Conference on ECAI 2010: 19th
European Conference on Artificial Intelligence, pages 145–150, 2010.
4. T. Economist. Data, data everywhere. The Economist, Feb 2010.
5. J. Howe. Crowdsourcing: Why the Power of the Crowd Is Driving the Future of Business.
Crown Publishing Group, New York, NY, USA, 1 edition, 2008.
6. X. Liu, M. Lu, B. C. Ooi, Y. Shen, S. Wu, and M. Zhang. Cdas: A crowdsourcing data
analytics system. Proc. VLDB Endow., 5(10):1040–1051, June 2012.
7. S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Freely available on the web,
2008.
8. Nature. Big data. Nature, Sept. 2008.
9. B. Yang and H. Garcia-Molina. Comparing hybrid peer-to-peer systems. In Proceedings of
the 27th International Conference on Very Large Data Bases, VLDB ’01, pages 561–570,
San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
10. M. Yang and Y. Yang. An efficient hybrid peer-to-peer system for distributed data sharing.
IEEE Transaction on Computer, 59(9):1158–1171, 2010.