-Peer-to-Peer networks are used by many applications to share resources between nodes. We have proposed a parallel version of a simulator for some aspects of a peerto-peer network performing file sharing. Being this analysis computationally expensive for contemporary CPUs, the computing power of Graphic Processing Units allows a great gain in performance during simulation. Specifically, we have used the NVIDIA Computer Unified Device Architecture programming model to simulate the behaviour of a peer-to-peer network performing data transfers, and compute communication delays as well as data updates. Index Terms-P2P networks, GPU computing, CUDA, Performance, Parallel
In the last few decades, the Peer-To-Peer (P2P) technology
and its many variants, such as BitTorrent, have become popular
Internet applications due to their scalability and robustness [
A sequential simulation of the behaviour of a P2P network is viable for a small amount of data and nodes that transfer data: the results can be achieved in a relatively short time. However, for an extensive analysis, the sequential approach is not ideal for computations, having to cope with a lot of data and transfer nodes. One of the possible solutions is to have a parallel approach using a Graphic Processing Unit (GPU) architecture. The multi-core architecture of a GPU, organized in threads, blocks and grids, shows its great potential for the said simulation thanks to the lower computation time than the sequential approach, particularly when increasing the number of nodes and data transfer (i.e. these are often file fragments). In this paper, we propose to use GPUs to perform a simulation of a P2P network that is closer to the real case. To this end, our work focuses on the implementation, and optimization of exponentiation operations on GPUs.
The contribution of this work is threefold: (i) first, we have developed and analyzed a sequential algorithm, implemented Copyright c 2016 held by the authors. in C language, that simulates some aspects of a P2P network; (ii) second, we have implemented a correspondent GPU algorithm using the capability of a GPU architecture through the Computer Unified Device Architecture (CUDA) C/C++ language; (iii) finally, we have compared the results between the two approaches.
Our paper is organized as follows: Section 2 provides an overview of the P2P model, while Section 3 provides an overview of the CUDA architecture. Section 4 describes the simulation approaches for the sequential and GPU parallel versions. Section 5 shows the experimental results and the comparison of execution measured times. In Section 6 we analyze the related work, and finally Section 7 provides conclusions and possible future work.
Low overhead; Quality of Service (QoS) of peers; Autonomy;
Robustness.
Over time, the more traditional client-server model based on
a centralized approach has become a decentralized architecture
for P2P networks [
A distributed network architecture is a P2P network if its
participants share a part of their own hardware resources, as
processing power, network link capability, storage capacity [
The P2P network must have the following properties [
Symmetry : nodes assume equal roles in the operation of the P2P system. In many designs this property is relaxed by the use of special peer roles such as super peers or relay peers.
Autonomy : participation of the peer in the P2P system is determined locally, and there is no single administrative context for the P2P system.
Scalable : this is a pre-requisite of operating P2P systems with millions of simultaneous nodes, and means that the resources used at each peer exhibit a growth rate as a function of overlay size that is less than linear. It also means that the response time does not grow more than linearly as a function of overlay size.
Self-organization : the organization of the P2P system
increases over time using local knowledge and local
operations at each peer, and no peer dominates the system.
Biskupski, Dowling, and Sacha [
Stability : within a maximum variability rate, the P2P system should be stable, i.e., it should maintain its connected graph and be able to route deterministically within a practical hop-count bounds.
Figure 1 provides a conceptual representation of the P2P overlay topology. Since P2P networks are fault-tolerant, not susceptible to single-point-of-failure, P2P overlay topologies are multiply-connected. Broadly, there are three classes of P2P systems:
Pure P2P Systems, in which 2 nodes/devices interact with each other without requiring the intervention of any central server or service.
Hybrid P2P Systems, in which peers rely partially on a central server to provide certain services, although the interaction between peers still takes place independently. Federated P2P Systems, in which peer interactions take place inside pre-defined domains, such as within an organization.
In this classification we have an increasing degree of centralization.
Moreover, P2P systems can either be: (i) structured [
In this paper we consider a Structured and Pure P2P network.
CUDA is a parallel computing platform and programming model invented by NVIDIA. It enables an increase in computing performance by harnessing the power of GPUs. With millions of CUDA-enabled GPUs sold to date, software developers, scientists and researchers are finding broad-ranging uses for GPU computing with CUDA. Here are a few examples: (i) identify hidden plaque in arteries (heart attacks are the leading cause of death worldwide); (ii) analyze air traffic flow, the National Airspace System manages the nationwide coordination of air traffic flow. Computer models help identify new ways to alleviate congestion and keep airplane traffic moving efficiently. Using the computational power of GPUs, a team at NASA obtained a large performance gain, reducing analysis time from ten minutes to three seconds. The speed-up is the result of the parallel GPU architecture, which however require developers to port compute-intensive portions of the application to the GPU using the CUDA Toolkit.
CUDA works, conceptually, according to the architectural model shown in Figure 2. The graphic chip, in the CUDA model, is constituted by a series of multiprocessors, called Streaming MultiProcessor. The number of multiprocessors depends on the characteristics specific to the class and performance of each GPU. Each processor can perform a mathematical operation (sum, multiplication, subtraction, etc.) on integers or floating point single-precision numbers (32-bit). In each processor there are also two multi-unit. Special functions are given (that perform transcendent as sine, cosine, reverse etc.) and, only for chips based on GT200 architecture, a single unit in floating-point double-precision (64-bit) is available. In a multiprocessor there is a shared memory accessible by all streaming processors, cache for instructions. The other types of memory, as shown in the picture, are accessible by each processor and represent the main repository for large amounts of data to be saved in the GPU. In the following we analyze the parts of code in the GPU using the libraries provided by NVIDIA.
CUDA programming indicates as a kernel function a portion of code that runs in parallel, N times.
The individual run of the kernel is performed by a simple unit called thread. CUDA threads are simpler than CPU threads, so the code is considered to be faster. To determine the number of threads that run a single kernel there is a logical organization and a two-level hierarchy. In the top level they depend on the size of a grid. The grid is a two-dimensional level comprising blocks that in turn have a three-dimensional structure that is specified by the number of threads.
Once a kernel is launched it receives two structures specifying the additional parameters for the size of grid and blocks. This listing shows the syntax to launch a kernel function named kernelfunction(). dim3 blocksize(x, y, z); dim3 gridsize (x, y); kernelfunction <<<gridsize, blocksize>>>(parameters); Listing 1. Kernel syntax
The logical division in grid and blocks is a crucial aspect in the design and code, in CUDA. In addition to the limits imposed by the hardware, there are other precautions that should be taken into account to make code more efficient.
A P2P-based application is a distributed application that provides tasks or work loads to peers, which have the same privileges. Peers give a portion of their resources available to other network participants, they need not a central coordination server. A P2P system can be used in many application domains, e.g. in social contexts, like sharing files and resources. Today, given the large diffusion of P2P networks we need to simulate and assess the performance of novel transfer protocols, in terms of the computation time and how many nodes are involved into the communication. Generally, according to the increase of nodes and files, the computation time increases.
In our simulation, we suppose that each peer communicates with others. Each peer has some file fragments and shares them, while at the same time receives the missing parts of some files. The peers and file fragments are represented in an array with N peers and M fragments, while the latency times of communication between nodes (namely ping) are in an array N*M, named p.
On top of figure 3 it is shown the initial state of the peers, in terms of availability of file fragments. We can see that a single node has some file fragments: 0 represent the absent state, while the 1 represent the available state. On the bottom it is shown the final state of the peers, after the fragments have been transferred between peers.
The first approach is the sequential one. Listing 2 shows the algorithm in C language, with the selection of peers that will receive the file fragments and update their state (from absent to available). Constant N is the number of peers, and M is the number of fragments. Array rics contains the destination peer indexes. There are MAXINS destination peers for a source peer, which are sequentially counted starting from the index of the source peer.
The update of file fragments consists of comparing for each source peer, having index tidx, its fragments availability, as determined by array f, with the fragments availability of a peer having index rics[i]. If the difference between source and destination is equal to zero, there will not be an update, else the source will send missing fragments to the destination peer. To approximate the real case, in the simulation we use the latency times for each fragment transfer, both in download and in upload. In this analysis we assume that the transfer is ideal, i.e. no loss of packets occurs. The simulation has to consider each source peer, file fragment and destination peer, therefore we have three nested for cicles.
This approach is viable for a few peers and fragments, i.e. the results can be obtained in a small amount of time. However, the sequential approach is not appropriate for many peers and fragments, the solution is then a parallel approach using a GPU architecture. void chooseNode(int tidx, int *rics){ for (int i=0; i < MAXINS; i++)
rics[i] = ((tidx + i + 1) % N); } int checkFr(int *f, int tidx, int *rics, int tidy, int i){ if (f[tidx*N + tidy] - f[rics[i]*N + tidy]) return 1; return 0; } }
} void selection(float *p, int *f) { int rics[MAXINS]; unsigned long tidx; unsigned long tidy; for (tidx=0; tidx <= N; tidx++) { chooseNode(tidx, rics); for (tidy=0; tidy <= M; tidy++) for (int i=0; i < MAXINS; i++) if (checkFr(f, tidx, rics, tidy, i)) if (p[tidx*N + tidy] <= tstep*(tidx*N + tidy))
f[rics[i]*N + tidy] = 1;
Listing 2. Sequential algorithm updating fragments availability
The multi-core architecture of GPU, organized in threads,
blocks and grids [
Indeed the kernel is executed in parallel by threads, which are organized in blocks, with a 3D structure, and grids with a 2D structure. For simulating a P2P network we use a 2D array, with ThreadIdx.x indicating the nodes and ThreadIdx.y indicating the fragments. As in the sequential algorithm, we check on each peer whether fragments are available. We use the device function checkFr() for this, whose body is the same as the corresponding function in listing 2. If the fragment is avalaible, the state of the peer can be updated in due time. This global function runs in parallel in each GPU’s core thanks to indexes tidx and tidy. __global__ void selection(float *p, int *f){ int rics[MAXINS]; unsigned long tidx = blockIdx.x*blockDim.x + threadIdx.x; unsigned long tidy = blockIdx.y*blockDim.y + threadIdx.y; } chooseNode(tidx, rics); for (int i = 0; i < MAXINS; i++) if (checkFr(f, tidx, rics, tidy, i)) if (p[tidx*N + tidy] <= tstep*(tidx*N + tidy)) f[rics[i]*N + tidy] = 1;
The keyword global indicates a kernel function that runs on the device and is called from host code, and runs in multiple instances on several blocks and threads. Listing 3 shows the kernel function for our simulation. cudaMalloc((void**)&dev_p,N*M*sizeof(float)); cudaMalloc((void**)&dev_f,N*M*sizeof(int)); cudaMalloc((void**)&dev_dt,N*M*sizeof(float));
cudaMemcpy(dev_p,ping,N*M*sizeof(float), cudaMemcpyHostToDevice); cudaMemcpy(output,dev_f,N*M*sizeof(float), cudaMemcpyDeviceToHost);
Library function cudaMalloc() allocates a given size of
bytes of linear memory on the device and returns *devPtr, a
pointer to the allocated memory (see Listing 4). The allocated
memory is suitably aligned for any kind of variable. Function
cudaMalloc() returns a cudaErrorMemoryAllocation in case of
failure [
In function main() we invoke our kernel function selection() (see Listing 6), which allows to transfer the data from host to device. This performs the GPU computation, and then there is a cudaMemcpy() function call, copying from device to host the data indicating updated nodes. 500
The input arrays of ping times, node and their fragment availability are initially loaded from files. Every time-step the kernel is called and the output array is updated according to the latency time.
V. RESULTS FOR THE SEQUENTIAL AND GPU VERSIONS From the analysis of sequential and the GPU execution times, we can see that the result is very different with a high number of nodes and file fragments. With a small number of nodes, the sequential computation is faster than the parallel one, because the allocation in memory, that the CUDA compiler does through the GPU’s cores, is an expensive process, but this impact is smaller with the increase of nodes and data. The execution time has been obtained from the average of ten measures.
The sequential algorithm for processing data is executed on
a AMD(R) Athlon 64 X2 processor with up to 2.9 GHz clock
speed and 4GB of DDR3L-1333 RAM, while for the GPU
algorithm we used a Nvidia(R) GeForce(TM) GTX 480 with
480 CUDA cores and 1536 MB GDRR5 video RAM [
Figure 4, 5 and 6 show the execution times for the sequential (CPU) and parallel (GPU) versions, when considering a number of destination nodes equal to 1/25, 1/10 and 1/5, respectively, of the total nodes N . Indeed with a low N the perfomance of the CPU version are better because for the execution of the GPU version the memory allocation from host to device is a costly operation.
Figure 7 shows the comparison of three simulations, to appreciate the increasing difference in terms of execution time between the two approaches, with a strong dependence on the number of destination hosts MAXINS. Table I shows the actual measured times for all considered scenarios. e 100 m i t n o i t u c ex 50 E
0 e 100 m i t n o i t u c ex 50 E 0
Fig. 6. GPU and CPU execution time with MAXINS=1/5 of total nodes Figure 8 shows the ratio between execution times on CPU and GPU when varying the numer of MAXINS. The highest ratio is when the number of destination peers is highest. This indicates that the parallel version performs much better than the sequential version. Figure 9 provides the execution times on CPU and GPU with 50 destination nodes, when varying the number of peers. GPU performances are alway better than CPU performances, and when the number of peers is the highest also is the gain by resorting to GPU. Table II shows the actual measured times for the latter scenarios considered.
Nowadays, computational resources are available on
demand and tools are needed to coordinate their use [
Fig. 9. GPU and CPU execution times with MAXINS=50 nodes of shared files, i.e. how to have users contribute with contents that can be uploaded by other users, respecting the latency time in download and upload.
Some works have studied the problem of computation in
P2P networks using the GPU approach vs the CPU approach.
In [
In this paper we developed two approaches: the first one
is the sequential one, which we have implemented as C
language. The second is the parallel approach, which uses
CUDA C/C++ language. In [
In our paper an important focus is the performance in terms
of time, with a comparison between GPU and CPU
computation. In [
We have presented a sequential and a parallel solution for the simulation of a P2P network and tested them in an ideal scenario, i.e. without collisions or missing data, and achieved considerable perfomance gains by using parallelism. Indeed in each simulated setting we appreciated that the GPU solution has a lower execution time than the sequential one for updating a peer state. This becomes more evident with the increase of peers and fragments. Particularly, the perfomance of the sequential approach is worst when increasing the number of destination peers, having an exponential increase of the execution time, versus the linear trend of a GPU solution.
In the future we can improve the simulation by including non-ideal effects as collisions, higher latency times in uploads and downloads, and the transfer of larger data other than our binary data.