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.