Presence monitoring or intrusion detection in a location/area are examples of decision-support applications. Decision-support applications are applications where monitoring is used to collect (heterogeneous) data and create situational awareness, which further requires decisions and/or actions. As such, decision-support software consists of different interconnected components with very diverse roles, whose communication and synchronization are essential for the application functionality and performance. Despite this complexity, software design for decision-support is often driven by short-term functional requirements and only supported by designers’ previous experience. In the current non-systematic approach, mistakes can be easily made, and can be very difficult to repair.

Many situations in the security domain require decision-making based on complex data, i.e., many variables which need to be taken into account before adequate decisions can be made. For example, in a surveillance scenario, the size and complexity of the area of interest, the mix of objects, and the unexpected behavior of suspects are just a few examples of complex variables to be analyzed in the process. Existing decision support systems provide some analysis, but are typically limited in the complexity they can handle. Therefore, users end up with simplified models which often suffer in the accuracy of their decisions and, ultimately, may lead to incorrect decisions. In this work, we present a framework that can scale to cope with the complexity and time requirements of real-world scenarios, while remaining flexible to handle the ad-hoc adaptation to the situation. We discuss the challenges and solutions for such a scalable and flexible system, and validate it using a target tracking scenario in urban environments of different sizes.

Heterogeneous platforms composed of multi-core CPUs and different types of accelerators, like GPUs and Xeon Phi, are becoming popular for data parallel applications. The heterogeneity of the hardware mix and the diversity of the applications pose significant challenges to exploiting such platforms. In this situation, an effective workload partitioning between processing units is critically important for improving application performance. This partitioning is a function of the hardware capabilities as well as the application and the dataset to be used. In this work, we present a systematic approach to solve the partitioning problem. Specifically, we use modeling, profiling, and prediction techniques to quickly and correctly predict the optimal workload partitioning and the right hardware configuration to use. Our approach effectively characterizes the platform heterogeneity, efficiently determines the accurate partitioning, and easily adapts to new platforms, different application types, and different datasets. Experimental evaluation on 13 applications shows that our approach delivers excellent performance improvement of 1.2$\times$–14.6$\times$over a single-processor execution, and accurate partitioning with in most cases below 10 percent performance gap versus an oracle-based partitioning.

Heterogeneous platforms integrating different types of processing units (such as multi-core CPUs and GPUs) are in high demand in high performance computing. Existing studies have shown that using heterogeneous platforms can improve application performance and hardware utilization. However, systematic methods to design, implement, and map applications to efficiently use heterogeneous computing resources are only very few. The goal of my PhD research is therefore to study such heterogeneous systems and propose systematic methods to allow many (classes of) applications to efficiently use them. After 3.5 years of PhD study, my contributions are (1) a thorough evaluation of a suitable programming model for heterogeneous computing, (2) a workload partitioning framework to accelerate parallel applications on heterogeneous platforms, (3) a modelling-based prediction method to determine the optimal workload partitioning, (4) a systematic approach to decide the best mapping between the application and the platform by choosing the best performing hardware configuration (Only-CPU, Only-GPU, or CPU+GPU with the workload partitioning). In the near future, I plan to apply my approach to large-scale applications and platforms to expand its usability and applicability.

This paper examines the impact of heavy churn on the robustness of decentralized social network-based Sybil defense (SNSD) schemes. Our analysis reveals that (i) heavy churn disintegrates the social overlay network that is fundamental to these schemes into multiple disconnected components, resulting in poor network connectivity, and (ii) a naive solution that adds links from each node to all its 2-hop neighbors improves network connectivity but comes at a significant cost of poor attack resilience of these schemes.

Heterogeneous platforms are mixes of different processing units. The key factor to their efficient usage is workload partitioning. Both static and dynamic partitioning strategies have been defined in previous work, but their applicability and performance differ significantly depending on the application to execute. In this paper, we propose an application-driven method to select the best partitioning strategy for a given workload. To this end, we define an application classification based on the application kernel structure -- i.e., The number of kernels in the application and their execution flow. We also enable five different partitioning strategies, which mix the best features of both static and dynamic approaches. We further define the performance-driven ranking of all suitable strategies for each application class. Finally, we match the best partitioning to a given application by simply determining its class and selecting the best ranked strategy for that class. We test the matchmaking on six representative applications, and demonstrate that the defined performance ranking is correct. Moreover, by choosing the best performing partitioning strategy, we can significantly improve application performance, leading to average speedup of 3.0x/5.3x over the Only-GPU/Only-CPU execution, respectively.

Due to increasingly large datasets, graph analytics - traversals, all-pairs shortest path computations, centrality measures, etc. - are becoming the focus of high-performance computing (HPC). Because HPC is currently dominated by many-core architectures (both CPUs and GPUs), new graph processing solutions have to be defined to efficiently use such computing resources. Prior work focuses on platform-specific performance studies and on platform-specific algorithm development, successfully proving that algorithms highly tuned to GPUs or multi-core CPUs can provide high performance graph analytics. However, the portability of such algorithms remains an important concern for many users, especially the many companies without the resources to invest in HPC or concerned about lock-in in single-use parallel techniques.

Summary Open Computing Language (OpenCL) is an open, functionally portable programming model for a large range of highly parallel processors. To provide users with access to the underlying platforms, OpenCL has explicit support for features such as local memory and vector data types (VDTs). However, these are often low‐level, hardware‐specific features, which can be detrimental to performance on different platforms. In this paper, we focus on VDTs and investigate their usage in a systematic way. First, we propose two different approaches (inter‐vdtandintra‐vdt) to use VDTs in OpenCL kernels, and show how to translate scalar OpenCL kernels to vectorized ones. After obtaining vectorized code, we evaluate the performance effects of using VDTs with two types of benchmarks: micro‐benchmarks and macro‐benchmarks. With micro‐benchmarks, we study the execution model of VDTs and the role of the compiler‐aided vectorizer on five devices. With macro‐benchmarks, we explore the changes of memory access patterns before and after using VDTs, and the resulting performance impact. Not only our evaluation provides insights into how OpenCL's VDTs are mapped on different processors, but it also indicates that using such data types introduces changes in both computation and memory accesses. Based on the lessons learned, we discuss how to deal with performance portability in the presence of VDTs. Copyright © 2014 John Wiley & Sons, Ltd.

Due to the diversity of processor architectures and application memory access patterns, the performance impact of using local memory in OpenCL kernels has become unpredictable. For example, enabling the use of local memory for an OpenCL kernel can be beneficial for the execution on a GPU, but can lead to performance losses when running on a CPU. To address this unpredictability, we propose an empirical approach: by disabling the use of local memory in OpenCL kernels, we enable users to compare the kernel versions with and without local memory, and further choose the best performing version for a given platform. To this end, we have designed Grover, a method to automatically remove local memory usage from OpenCL kernels. In particular, we create a correspondence between the global and local memory spaces, which is used to replace local memory accesses by global memory accesses. We have implemented this scheme in the LLVM framework as a compiling pass, which automatically transforms an OpenCL kernel with local memory to a version without it. We have validated Grover with 11 applications, and found that it can successfully disable local memory usage for all of them. We have compared the kernels with and without local memory on three different processors, and found performance improvements for more than a third of the test cases after Grover disabled local memory usage. We conclude that such a compiler pass can be beneficial for performance, and, because it is fully automated, it can be used as an auto-tuning step for OpenCL kernels.

Although GPUs are considered ideal to accelerate massively data-parallel applications, there are still exceptions to this rule. For example, imbalanced applications cannot be efficiently processed by GPUs: despite the massive data parallelism, a varied computational workload per data point remains GPU-unfriendly. To efficiently process imbalanced applications, we exploit the use of heterogeneous platforms (GPUs and CPUs) by partitioning the workload to fit the usage patterns of the processors. In this work, we present our flexible and adaptive method that predicts the optimal partitioning. Our method aims to match a quantitative model of the application with the hardware capabilities of the platform, and calculates the optimal match according to a user-given criterion. We evaluate our method in terms of overall performance gain, prediction accuracy, flexibility and adaptivity. Our results, gathered from both synthetic and real-world workloads, show performance gains of up to 60%, accurate predictions for more than 90% of all the 1395 imbalanced workloads we have tested, and confirm that the method adapts correctly to application, dataset, and platform changes (both hardware and software). We conclude that model-based prediction of workload partitioning for heterogeneous platforms is feasible and useful for performance improvement.

In recent years fully decentralized file sharing systems were developed aimed at improving anonymity among their users. These systems provide typical file sharing features such as searching for and downloading files. However, elaborate schemes originally aimed at improving anonymity cause partial keyword matching to be virtually impossible, or introduce a substantial bandwidth overhead. In this paper we introduce 4P, a system that provides users with anonymous search on top of a semantic overlay. The semantic overlay allows users to efficiently locate files using partial keyword matching, without having to resort to an expensive flooding operation. Included into 4P are a number of privacy enhancing features such as probabilistic query forwarding, path uncertainty, caching, and encrypted links. Moreover, we integrate a content retrieval channel into our protocol allowing users to start downloading a file from multiple sources immediately without requiring all intermediate nodes to cache a complete copy. Using a trace-based dataset, we mimic a real-world query workload and show the cost and performance of search using six overlay configurations, comparing random, semantic, Gnutella, RetroShare, and OneSwarm to 4P. The state-of-the-art flooding based alternatives required approximately 10,000 messages to be sent per query, in contrast 4P only required 313. Showing that while flooding can achieve a high recall (more than 85% in our experiments) it is prohibitively expensive. With 4P we achieve a recall of 76% at a considerable reduction in messages sent.

Based on Intel's Many Integrated Core (MIC) architecture, Intel Xeon Phi is one of the few truly many-core CPUs - featuring around 60 fairly powerful cores, two levels of caches, and graphic memory, all interconnected by a very fast ring. Given its promised ease-of-use and high performance, we took Xeon Phi out for a test drive. In this paper, we present this experience at two different levels: (1) the microbenchmark level, where we stress "each nut and bolt" of Phi in the lab, and (2) the application level, where we study Phi's performance response in a real-life environment. At the microbenchmarking level, we show the high performance of five components of the architecture, focusing on their maximum achieved performance and the prerequisites to achieve it. Next, we choose a medical imaging application (Leukocyte Tracking) as a case study. We observed that it is rather easy to get functional code and start benchmarking, but the first performance numbers can be far from satisfying. Our experience indicates that a simple data structure and massive parallelism are critical for Xeon Phi to perform well. When compiler-driven parallelization and/or vectorization fails, programming Xeon Phi for performance can become very challenging.

With the integration of more computational cores and deeper memory hierarchies on modern processors, the performance gap between naively parallel zed code and optimized code becomes much larger than ever before. Very often, bridging the gap involves architecture-specific optimizations. These optimizations are difficult to implement by application programmers, who typically focus on the basic functionality of their code. Therefore, in this thesis, I focus on answering the following research question: "How can we address architecture-specific optimizations in a programmer-friendly way?'' As an answer, I propose an optimizing framework for parallel applications running on many-core processors (\textit{Sesame}). Taking a simple parallel zed code provided by the application programmers as input, Sesame chooses and applies the most suitable architecture-specific optimizations, aiming to improve the overall application performance in a user-transparent way. In this short paper, I present the motivation for designing and implementing Sesame, its structure and its modules. Furthermore, I describe the current status of Sesame, discussing our promising results in source-to-source vectorization, automated usage of local memory, and auto-tuning for implementation-specific parameters. Finally, I discuss my work-in-progress and sketch my ideas for finalizing Sesame's development and testing.

The particle filter is a Bayesian estimation technique based on Monte Carlo simulation. It is ideal for non-linear, nonGaussian dynamical systems with applications in many areas, such as computer vision, robotics, and econometrics. Practical use has so far been limited, because of steep computational requirements. In this study, we investigate how to design a particle filter framework for complex estimation problems using many-core architectures. We develop a robotic arm application as a highly flexible estimation problem to push estimation rates and accuracy to new levels. By varying filtering and model parameters, we evaluate our particle filter extensively and derive rules of thumb for good configurations. Using our robotic arm application, we achieve a few hundred state estimations per second with one million particles. With our framework, we make a significant step towards a wider adoption of particle filters and enable studies into filtering setups for even larger estimation problems.

Recent parallel architectures are equipped with local memory, which simplifies hardware design at the cost of increased program complexity due to explicit management. To simplify this extra-burden that programmers have, we introduce an easy-to-use API, ELMO, that improves productivity while preserving high performance of local memory operations. Specifically, ELMO is a generic API that covers different local memory use-cases. We also present prototype implementations for these APIs and perform multiple GPU-inspired optimizations to maximize their performance. Experimental results on the NVIDIA Quadro5000 GPU show that performance is significantly improved by using ELMO on native implementations: the achieved speedup ranges from 1.3x to 3.7x. Furthermore, using ELMO we still achieve performance comparable (if not better) with that of hand-tuned applications, while the code is shorter, clearer, and safer.

With its design concept of cross-platform portability, OpenCL can be used not only on GPUs (for which it is quite popular), but also on CPUs. Whether porting GPU programs to CPUs, or simply writing new code for CPUs, using OpenCL brings up the performance issue, usually raised in one of two forms: "OpenCL is not performance portable!" or "Why using OpenCL for CPUs after all?!". We argue that both issues can be addressed by a thorough study of the factors that impact the performance of OpenCL on CPUs. This analysis is the focus of this paper. Specifically, starting from the two main architectural mismatches between many-core CPUs and the OpenCL platform-parallelism granularity and the memory model-we identify eight such performance "traps" that lead to performance degradation in OpenCL for CPUs. Using multiple code examples, from both synthetic and real-life benchmarks, we quantify the impact of these traps, showing how avoiding them can give up to 10 times better performance. Furthermore, we point out that the solutions we provide for avoiding these traps are simple and generic code transformations, which can be easily adopted by either programmers or automated tools. Therefore, we conclude that a certain degree of OpenCL inter-platform performance portability, while indeed not a given, can be achieved by simple and generic code transformations.

Real-time stereo matching, which is important in many applications like self-driving cars and 3-D scene reconstruction, requires large computation capability and high memory bandwidth. The most time-consuming part of stereo-matching algorithms is the aggregation of information (i.e. costs) over local image regions. In this paper, we present a generic representation and suitable implementations for three commonly used cost aggregators on many-core processors. We perform typical optimizations on the kernels, which leads to significant performance improvement (up to two orders of magnitude). Finally, we present a performance model for the three aggregators to predict the aggregation speed for a given pair of input images on a given architecture. Experimental results validate our model with an acceptable error margin (an average of 10.4%). We conclude that GPU-like many-cores are excellent platforms for accelerating stereo matching.

SUMMARY When computer architects reinvented parallelism through multi‐core processors, application parallelization became a problem. Now that multi‐cores have penetrated from handhelds to supercomputers, parallelization becomes a large‐scale challenge. A lot of research is going into compiler improvements, language extensions, frameworks and application/platform case studies. Whereas fairly successful, these solutions are based on experimental tools, trial‐and‐error, and expert knowledge, and do not bring multi‐core programming into reach for the whole software industry. We believe that the challenge of “mass parallelization” must be tackled more systematically. Development begins at application specification and algorithm design, followed by application characterization with trade‐offs in parallelization strategies and data layouts. Only with a proper software design, implementation and optimization can start. In this article, we focus on quantitative application characterization for such a systematic approach. We introduce a set of metrics to characterize applications and show how they can be used. We present our interpretation of the results and suggest ways to use them to guide design decisions. We conclude that metrics can be used to understand applications and design decisions early on. Therefore, this characterization brings us closer to effective parallel applications development for multi‐core processors. Copyright © 2011 John Wiley & Sons, Ltd.

During the last decade of P2P research a lot of attention has been given to incentive mechanisms. While centralized incentive mechanisms are straightforward in their design, a long term challenge has been to create a decentralized incentive mechanism that can be used to effectively induce cooperation and reduce freeriding. While there have been many proposals of such mechanisms based on the spreading of reputation information, little attention has been given to the theoretical limitations of such designs. In this paper, we present a high level model of reputation-based incentive mechanisms. We derive upper bounds on the effectiveness of such mechanisms, especially with respect to the performance under behavioral change and population turnover. Moreover, we assess the effectiveness of a reputation overlay in BitTorrent, and show that while its tit-for-tat reciprocity algorithm provides incentives for uploading on the short term, it reduces the benefits of an integrated long term incentive mechanism. All in all, we offer important insights for the design of future incentive systems.

This paper presents a comprehensive performance comparison between CUDA and OpenCL. We have selected 16 benchmarks ranging from synthetic applications to real-world ones. We make an extensive analysis of the performance gaps taking into account programming models, ptimization strategies, architectural details, and underlying compilers. Our results show that, for most applications, CUDA performs at most 30% better than OpenCL. We also show that this difference is due to unfair comparisons: in fact, OpenCL can achieve similar performance to CUDA under a fair comparison. Therefore, we define a fair comparison of the two types of applications, providing guidelines for more potential analyses. We also investigate OpenCL's portability by running the benchmarks on other prevailing platforms with minor modifications. Overall, we conclude that OpenCL's portability does not fundamentally affect its performance, and OpenCL can be a good alternative to CUDA.

Application development for many-core processors is predominately hardware-centric: programmers design, implement, and optimize applications for a pre-chosen target platform. While this approach may deliver very good performance, it lacks portability, being inefficient for applications that aim to use multiple architectures or large-scale parallel platforms with heterogeneous many-core nodes. In this work, we focus on application portability. Therefore, we propose an application-centric approach for developing parallel workloads for many-cores, and we make use of OpenCL to preserve portability until the very last optimization stages. We validate our application-centric approach using 3D body scan, a data intensive application with soft real-time constraints. Thus, we design and implement OCL-body scan (the portable OpenCL-based version of 3D Body scan), and we evaluate its performance on three families of platforms - general purpose multi-cores, graphical processing units, and the Cell/B.E.. Our experiments show that our application-centric strategy enables portability and leads to good performance results. Additionally, typical platform-specific optimizations can be applied in the final implementation stages, leading to performance results similar to those obtained using the native tool-chains.

The efficiency of BitTorrent in content distribution has inspired a number of peer-to-peer (P2P) protocols for on-demand video (VoD) streaming systems (henceforth BitTorrent-like VoD systems). However, the fundamental quality-of-service (QoS) requirements of VoD (i.e. providing peers with a smooth playback continuity and a short startup delay) make the design of these systems more challenging than normal file-sharing systems. In particular, the bandwidth allocation strategy is an important aspect in the design of BitTorrent-like VoD systems, which becomes even more crucial in a scenario where a large number of peers joins in a short period of time, a phenomenon known as flashcrowd. In fact, the new joining peers all demand for content while having few or no pieces of content to offer in return yet. An unwise allocation of the limited bandwidth actually available during this phase may cause peers to experience poor QoS. In this work, we analyze the effects of a flashcrowd on the scalability of a BitTorrent-like VoD system and propose a number of mechanisms to make the bandwidth allocation in this phase more effective. In particular, we derive an upper bound for the number of peers that can be admitted in the system over time and we find that there is a trade-off between having the seeders minimize the upload of pieces already injected recently and high peer QoS. Based on the insights gained from our analysis, we devise some flashcrowd-handling algorithms for the allocation of peer bandwidth to improve peer QoS during flashcrowd. We validate the effectiveness of our proposals by means of extensive simulations.

Distributed systems without a central authority, such as peer-to-peer (P2P) systems, employ incentives to encourage nodes to follow the prescribed protocol. Game theoretic analysis is often used to evaluate incentives in such systems. However, most game-theoretic analyses of distributed systems do not adequately model the repeated interactions of nodes inherent in such systems. We present a game-theoretic analysis of a popular P2P protocol, Bit-Torrent, that models the repeated interactions in such protocols. We also note that an analytical approach for modeling incentives is often infeasible given the complicated nature of most deployed protocols. In order to comprehensively model incentives in complex protocols, we propose a simulation-based method, which we call Design Space Analysis (DSA). DSA provides a tractable analysis of competing protocol variants within a detailed design space. We apply DSA to P2P file swarming systems. With extensive simulations we analyze a wide-range of protocol variants and gain insights into their robustness and performance. To validate these results and to demonstrate the efficacy of DSA, we modify an instrumented BitTorrent client and evaluate protocols discovered using DSA. We show that they yield higher system performance and robustness relative to the reference implementation.

Most P2P systems that have some kind of incentive mechanism reward peers according to their contribution, i.e. total bandwidth offered to the system. Due to the disparity in bandwidth capacity between P2P users on the Internet, the common effect of such mechanisms is that the fastest peers reap the highest benefits. We take a different approach and study how to incentivize cooperation in P2P systems based on effort, i.e. contribution relative to capacity. We make the following contributions: 1) we argue that contribution-based incentive schemes in P2P systems unnecessarily disfavor slow peers and decrease overall system performance; 2) we advocate the use of principles from an alternative economic vision, Participatory Economics (Parecon), to inspire systems to be fair and to ensure maximization of the social welfare while being efficient at the same time, and 3) we present the results of simulations in which we apply principles from Parecon to two popular real life systems: a) the popular file sharing BitTorrent protocol; b) a generic credit based sharing ratio enforcement scheme. Our approach yields a higher system performance and fairness and offers new insights into P2P incentive design.

The efficiency of Bit Torrent in disseminating content has inspired a number of P2P protocols for on-demand video streaming (VoD). Prior work on adapting Bit Torrent to VoD mainly focused on the piece selection policy, since streaming requires a somewhat "in order" download progress. Conversely, not much effort has been spent into adapting Bit Torrent's peer selection policy, where nodes mainly serve those that have recently uploaded to them at the highest rates. This mechanism incentivizes cooperation among peers but, in a heterogeneous system (i.e. where peers have different bandwidth capacities), it causes faster peers to receive higher download speeds than slower peers. This might hurt the system's ability of providing as many nodes as possible with the minimum download speed necessary to sustain the video playback rate. Furthermore, peers gain little utility in downloading at rates much higher than the video playback rate. Inspired by these observations, in this work, we extend the peer selection mechanism of an existing Bit Torrent-like VoD protocol, give-to-get (G2G), with techniques that allow peers to relax their reciprocity-based peer selection and choose more random nodes when their current QoS is high. In this way, more peers can be granted a good QoS and free-riding is tolerated only when bandwidth resources are abundant. To demonstrate the benefits of our approach, we present extensive simulations of the introduced techniques.

A well-known problem in P2P systems is freeriding, where users do not share content if there is no incentive to do so. In this paper, we distinguish lazy freeriders that are merely reluctant to share but follow the protocol, versus die-hard freeriders that employ sophisticated methods to subvert the protocol. Existing incentive designs often provide theoretically attractive resistance against die-hard freeriding, yet are rarely deployed in real networks because of practical infeasibility. Meanwhile, real communities benefit greatly from prevention of lazy freeriding, but have only centralized technology available to do so. We present a lightweight, fully distributed mechanism called BARTERCAST that prevents lazy freeriding and is deployed in practice. BarterCast uses a maxflow reputation algorithm based on a peer's private history of its data exchanges as well as indirect information received from other peers. We assess different reputation policies under realistic, trace-based community conditions and show that our mechanism is consistent and effective, even when significant fractions of peers spread false information. Furthermore, we present results of the deployment of BarterCast in the BitTorrent-based Tribler network which currently has thousands of users worldwide.

The explosion of freely available media content through BitTorrent file sharing networks over the Internet means that users need guides or recommendations to find the right, high quality, content. Current systems rely on centralized servers to aggregate, rate and moderate metadata for this purpose. We present the design and simulations, using real BitTorrent traces, for a method combining fully decentralized metadata dissemination, vote sampling and ranking for deployment in the Tribler.org BitTorrent media client. Our design provides robustness to spam attacks, where metadata does not reflect the content it is attached to, by controlling metadata spreading and by vote sampling based on a collusion proof experience function. Our design is light-weight, fully decentralized and offers good performance and robustness under realistic conditions.

The BitTorrent protocol is by far the most popular protocol for offline peer-to-peer video distribution on the Internet. BitTorrent has previously been extended to support the streaming of recorded video, that is, Video-on-Demand (VoD). In this paper, we take this support for video streaming a step further by presenting extensions to BitTorrent for supporting live video streaming, which we have implemented in our BitTorrent client called Tribler. We have tested our extensions both by running simulations, and by deploying our implementation in a public trial in the Internet, using the optimal values of several parameters as found in the simulations. We analyse the performance of Tribler in systems with varying values for the percentage of peers behind a firewall or NAT, which we consider to be one of the key parameters in the performance of deployed P2P systems. Our public trial lasted 9 days, during which 4555 unique peers participated from around the globe. We found 61% of the peers to be behind a firewall, a level at which our simulations still indicate acceptable performance. Most of the peers indeed obtained good performance, with for instance a very low prebuffering time before playback starts, indicating the feasibility of our approach. The median prebuffering time we measured was 3.6 seconds, which is 3-10 times shorter than the prebuffering time measured in other deployed peer-to-peer systems.

A number of analytical models exists that capture various properties of the BitTorrent protocol. However, until now virtually all of these models have been based on the assumption that the peers in the system have homogeneous bandwidths. As this is highly unrealistic in real swarms, these models have very limited applicability. Most of all, these models implicitly ignore BitTorrent's most important property: peer selection based on the highest rate of reciprocity. As a result, these models are not suitable for understanding or predicting the properties of real BitTorrent networks. Furthermore, they are hardly of use in the design of realistic BitTorrent simulators and new P2P protocols. In this paper, we extend existing work by presenting a model of a swarm in BitTorrent where peers have arbitrary upload and download bandwidths. In our model we group peers with (roughly) the same bandwidth in classes, and then analyze the allocation of upload slots from peers in one class to peers in another class. We show that our model accurately predicts the bandwidth clustering phenomenon observed experimentally in other work, and we analyze the resulting data distribution in swarms. We validate our model with experiments using real BitTorrent clients. Our model captures the effects of BitTorrent's well-known `tit-for-tat' mechanism in bandwidth-inhomogeneous swarms and provides an accurate mathematical description of the resulting dynamics.

With Peter Knijnenburg's passing away earlier this year we lost a great scientist, colleague and friend. Peter made significant contributions in many areas and is probably best known for his work on iterative compilation where he showed creative insight many years before the subject became mainstream. Peter was unusual in that he was highly versatile in his thinking and approach. This is probably best illustrated by his ability to move from physics to the ‘theory of theories’—category theory and then on to linear algebraic program frameworks, iterative compilation and SMT quality of service. He was a highly prolific researcher publishing many papers in his short academic life and working with over 90 different co-authors. He possessed exceptional analytical skills and was able to succinctly communicate his research contributions. He was generous with his time and ideas. For many Peter Knijnenburg will be remembered for his warm hospitality when hosting the CPC workshop in Amsterdam 2003. Peter's passing is a great loss to the research community. He is sadly missed and will always be remembered with affection by his colleagues.

Abstract Applications running on multicore platforms are difficult to program, and even more difficult to optimize, mainly due to (1) the several layers where the optimizations occur and (2) the multitude of available resources to be exploited in parallel. Although low‐level optimizations only target code running on individual cores, high‐level optimizations (e.g. data‐ and task‐parallelism) target the overall application performance. In this paper, we focus on the latter, by evaluating possible mapping scenarios of a real application on a heterogeneous multicore processor. Specifically, we focus on analyzing the impact of combining data‐ and task‐parallelism for a multimedia analysis application running on the Cell Broadband Engine (Cell/B.E.). We find that both low‐level and high‐level optimizations are important for the overall application speed‐up. However, we show that a speed‐up factor of over 20 for the application running on Cell/B.E. can only be obtained if core utilization is increased by combining data‐ and task‐parallelism. Thus, we consider this case study essential for building expertise in both application optimization and performance analysis for multicore platforms. Copyright © 2008 John Wiley & Sons, Ltd.

The popular and well-known BitTorrent peer-to-peer protocol offers fast file distribution in a highly scalable way. Several studies have investigated the properties of this protocol, mostly focusing on heterogeneous end-user environments such as the Internet, with asymmetric connections. In this paper however, we focus on the usage of the BitTorrent protocol in homogeneous local environments with symmetric bandwidth properties. Compared with a traditional client-server setup, the use of BitTorrent in such settings can offer huge benefits in performance and scalability, allowing bandwidth sharing and high speed file distribution. We aim to improve the performance of such networks with a novel mechanism for replication using so-called replicators, which replicate a subset of the files in the system. A mathematical model of the resulting Replicated BitTorrent is presented and validated by emulation. Furthermore, we present simulation results that provide insight in the performance of Replicated BitTorrent networks with dynamic peer arrivals and departures. The results show that Replicated BitTorrent significantly improves download times in local bandwidth-symmetric BitTorrent networks.

Peer-to-peer file-sharing networks depend on peers uploading data to each other. Some peers, called free-riders, will not upload data unless there is an incentive to do so. Algorithms designed to prevent free-riding typically assume that connectivity is not a problem. However, on the Internet, a large fraction of the peers resides behind a firewall or NAT, making them unable to accept incoming connections. In this paper, we will prove that it is impossible to prevent free-riding when more than half of the peers are firewalled, and we will provide bounds on the sharing ratios (defined as the number of bytes uploaded divided by the number of bytes downloaded) of both firewalled and non-firewalled peers. Firewall puncturing techniques are complex but can be used to connect two firewalled peers; we will provide a bound on their required effectiveness in order to achieve fairness.We confirm our theory by simulating individual BitTorrent swarms (sets of peers that download the same file), and show that the theoretical bounds can be met in systems with many firewalled peers. We have also collected statistics covering thousands of BitTorrent swarms in several communities, both open and closed; the latter ban peers if their sharing ratios drop below a certain treshhold. We found 45% of the peers to be firewalled in the closed communities, as opposed to 66% in the open communities, which correlates with our theory that to obtain fair sharing ratios for all peers, at most half of them can be behind firewalls.

Abstract Most current peer‐to‐peer (P2P) file‐sharing systems treat their users as anonymous, unrelated entities, and completely disregard any social relationships between them. However, social phenomena such as friendship and the existence of communities of users with similar tastes or interests may well be exploited in such systems in order to increase their usability and performance. In this paper we present a novel social‐based P2P file‐sharing paradigm that exploits social phenomena by maintaining social networks and using these in content discovery, content recommendation, and downloading. Based on this paradigm's main concepts such as taste buddies and friends, we have designed and implemented the TRIBLER P2P file‐sharing system as a set of extensions to BitTorrent. We present and discuss the design of TRIBLER, and we show evidence that TRIBLER enables fast content discovery and recommendation at a low additional overhead, and a significant improvement in download performance. Copyright © 2007 John Wiley & Sons, Ltd.

In this paper we present a solution for efficient porting of sequential C++ applications on the Cell B.E. processor. We present our step-by-step approach, focusing on its generality, we provide a set of code templates and optimization guidelines to support the porting, and we include a set of equations to estimate the performance gain of the new application. As a case-study, we show the use of our solution on a multimedia content analysis application, named MARVEL. The results of our experiments with MARVEL prove the significant performance increase in favor of the application running on Cell when compared with the reference implementation.

The main purpose of many current peer-to-peer (P2P) networks is off-line file sharing. However, a potentially very promising use of such networks is to share video streams (e.g., TV programs) in real time. In order to do so, the peers in a P2P network who are interested in the same video stream may employ Application Level Multicasting (ALM). In existing P2P networks, peers may exhibit behavior which is problematic for ALM: they are not always willing to donate resources (free-riding), and they may arrive and depart at a high rate (churn). In this paper we propose the Orchard algorithm for creating and maintaining ALM trees in P2P networks, which deals with both these problems. By employing a technique called Multiple Description Coding, we split a video stream into several substreams. Orchard creates a dynamic spanning tree for each of these substreams in such a way that in the resulting forest, no peer has to forward more substreams than it receives. Based on an analysis of the expected performance of Orchard and on experiments in a real system, we find that Orchard is capable of maintaining a multicast forest, even when peers join and leave the forest at a high rate.

The main purpose of many current peer-to-peer (P2P) networks is off-line file sharing. However, a potentially very promising use of such networks is to share video streams (e.g., TV programs) in real time. In order to do so, the peers in a P2P network who are interested in the same video stream may employ application level multicasting (ALM). In existing P2P networks, peers may exhibit behaviour which is problematic for ALM: peers tend not to donate any resources (free-riding), and they arrive and depart at a high rate (churn). In this paper we propose the orchard algorithm for ALM of video streams in P2P systems, which deal with both these problems. By employing a technique called multiple description coding, we split a video stream into several substreams. Orchard creates a dynamic spanning tree for each of these substreams in such a way that in the re suiting forest, no peer has to forward more substreams than it receives. Our experiments show that orchard is capable of providing a good quality of service to every peer, even when peers join and leave the forest at a high rate

Abstract Java classes are very flexible, but this comes at a price. The main cost is that every class instance must be dynamically allocated. Also, their access by reference introduces pointer de‐references and complicates program analysis. These costs are particularly burdensome for small, ubiquitous data structures such as coordinates and state vectors. For such data structures a lightweight representation is desirable, allowing such data to be handled directly, similar to primitive types. A number of proposals introduce restricted or mutated variants of standard Java classes that could serve as lightweight representation, but the impact of these proposals has never been studied. Since we have implemented a Java compiler with lightweight data structures we are in a good position to do this evaluation. Our lightweight data structures are tuples. As we will show, using tuples can result in significant performance gains: for a number of existing benchmark programs we gain more than 50% in performance relative to our own compiler, and more than 20% relative to Sun's Hotspot 1.4 compiler. We expect similar performance gains for other implementations of lightweight data structures. With respect to the expressiveness of Java, lightweight variants of standard Java classes have little impact. In contrast, tuples add a different language construct that, as we will show, can lead to substantially more concise program code. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract Streaming multimedia content in real‐time over a wireless link is a challenging task because of the rapid fluctuations in link conditions that can occur due to movement, interference, and so on. The popular IEEE 802.11 standard includes low‐level tuning parameters like the transmission rate. Standard device drivers for today's wireless products are based on gathering statistics and consequently, adapt rather slowly to changes in conditions. To meet the strict latency requirements of streaming applications, we designed and implemented an advanced hybrid control algorithm that uses signal‐strength (SNR) information to achieve fast responses. Since SNR readings are quite noisy, we do not use that information to directly control the rate setting, but rather as a safeguard limiting the range of feasible settings to choose from. We report on real‐time experiments involving two laptops equipped with IEEE 802.11a wireless interface cards. The results show that using SNR information greatly enhances responsiveness in comparison to statistics‐based rate controllers. Finally, we will present the results of an experiment with real‐time video streaming to a moving laptop in an office‐like environment. Our hybrid control algorithm effectively prevented many packet losses, thereby achieving a much higher video quality than the statistics‐based algorithm. Copyright © 2005 John Wiley & Sons, Ltd.

In industry, embedded systems for stream-based processing are often modelled and verified by using process networks, such as Kahn process networks. An advantage of Kahn networks is that they allow asynchronous operation of process components in a network. A problem in these networks, however, is that asynchronously interfering events cannot be handled properly because they are intrinsically indeterminate and therefore destroy the compositional properties of the network. We propose to extend the Kahn model of computations with a simple indeterminate construct. We call the resulting network a context-aware process network (CAPN). We show that these networks are capable of handling certain classes of events and can still be reduced to a class of parametrised Kahn networks.

Abstract We present a set of language extensions that improve the expressiveness and performance of Java for scientific computation. The language extensions allow the manipulation of multi‐dimensional arrays to be expressed more naturally, and to be implemented more efficiently. Furthermore, data‐parallel programming is supported, allowing efficient parallelization of a large class of operations on arrays. We also provide language extensions to construct specialized array representations, such as symmetric, block, and sparse matrices. These extensions are: tuples, parameterized types, array subscript overloading, and the inline modifier. These extensions are not only useful in the construction of special array representations, but are also useful in their own right. Finally, we add complex numbers as a primitive type to the language. We evaluate our language extensions using performance results. We also compare relevant code fragments of our extended language with standard Java implementations and language extensions proposed by others. Copyright © 2003 John Wiley & Sons, Ltd.

Clock (and voltage) scheduling is an important technique to reduce the energy consumption of processors that support voltage scaling. It is difficult, however, to achieve good results using only statistics from the operating system level when applications show bursty (unpredictable) behavior. We take the approach that such applications must be made power-aware and specify their average execution time (AET) and the deadline to the scheduler controlling the clock speed and processor voltage. This paper describes our energy priority scheduling (EPS) algorithm supporting power-aware applications. EPS orders tasks according to how tight their deadlines are and how often tasks overlap. Low-priority tasks are scheduled first, since they can be easily preempted to accommodate for high-priority tasks later. The EPS algorithm does not always yield the optimal schedule, but has a low complexity. We have implemented EPS on a StrongARM-based variable-voltage platform. We conducted experiments with a modified video decoder that estimates the AET of each frame. Measurements show that application-directed voltage scaling reduces processor power consumption with 50% for the bursty video decoder without missing any frame deadlines.

Abstract High‐Performance Fortran (HPF) has been designed to provide portable performance on distributed memory machines. An important aspect of portable performance is the behavior of the available HPF compilers. Ideally, a programmer may expect comparable performance between different HPF compilers, given the same program and the same machine. To test the performance portability between compilers, we have designed a special benchmark suite, called the TNO HPF benchmark suite. It consists of a set of HPF programs that test various aspects of efficient parallel code generation. The benchmark suite consists of a number of template programs that are used to generate test programs with different array sizes, alignments, distributions, and iteration spaces. It ranges from very simple assignments to more complex assignments such as triangular iteration spaces, convex iteration spaces, coupled subscripts, and indirection arrays. We have run the TNO HPF benchmark suite on three compilers: the PREPARE prototype compiler, the PGI‐HPF compiler, and the GMD Adaptor HPF compiler. Results show performance differences that can be quite large (up to two orders of magnitude for the same test program). Closer inspection reveals that the origin of most of the differences in performance is due to differences in local enumeration and storage of distributed array elements. Copyright © 2002 John Wiley & Sons, Ltd.

Clock (and voltage) scheduling is an important technique to reduce energy consumption of variable-voltage processors. It is dicult, however, to achieve good results at the OS and hardware level when applications show bursty behavior. We take the approach that such applications must be made power aware and specify their future demands to a central scheduler controlling the clock speed and processor voltage. This paper describes our energy priority scheduling (EPS) heuristic that orders tasks according to how tight their deadlines are and how often tasks overlap. We schedule low-priority tasks rst, since they can be easily preempted to accommodate for high-priority tasks later. The EPS heuristic does not always yield the optimal schedule, but has low complexity and can be used as an incremental on-line algorithm. We implemented EPS on a StrongARM-based variable-voltage platform. Measurements show that EPS reduces energy consumption with 50% for a bursty video decoding application without missing any frame deadlines.

Power consumption is the limiting factor for the functionality of future wearable devices. Since interactive applications like wireless information access generate bursts of activities, it is important to match the performance of the wearable device accordingly. This paper describes a system with a microprocessor whose speed can be varied (frequency scaling) as well as its supply voltage. Voltage scaling is important for reducing power consumption to very low values when operating at low speeds. Measurements show that the energy per instruction at minimal speed is 1/5 of the energy required at full speed. The frequency and voltage can be scaled dynamically from user space in only 140 μs. This allows power-aware applications to quickly adjust the performance level of the processor whenever the workload changes. Experiments with an H.263 video benchmark show that the power-aware decoder outperforms a static fixed-frequency policy as well as a dynamic interval-based scheduler.

A major problem in the development of distributed applications is that one cannot assume that the environment in which the application is to operate will remain the same. This means that developers must take into account that the application should be easy to adapt, A requirement that is often formulated imprecisely is that an application should be scalable. The authors concentrate on scalability as a requirement for distributed applications, what it actually means, and how it can be taken into account during system design and implementation. They present a framework in which scalability requirements can be formulated precisely. In addition, they present an approach by which scalability can be taken into account during application development. Their approach consists of an engineering method for distributing functionality, combined with an object-based implementation framework for applying scaling techniques such as replication and caching.

We present Spar, a programming language for semi-automatic parallel programming, in particular for the programming of array-based applications. The language has been designed as part of the Automap project, in which a compiler and runtime system are being developed for distributed-memory systems. As suggested by its name, Automap aims at completely automatic code and data mapping at either compile time or runtime. This relieves the programmer of a difficult task, and makes Spar programs completely portable. Apart from a few minor modifications, Spar is a superset of Java. This provides Spar with a modern, solid, language as its basis, and makes Spar more accessible. Spar extends Java with constructs forparallel programming, extensive support for array manipulation, and a number of other powerful language extensions. © 1997 John Wiley & Sons, Ltd.

In this paper, we analyze the efficiency of three local enumeration and three storage compression schemes for cyclic(m) data distributions in High Performance Fortran (HPF).We show that for linear array access sequences, efficient enumeration and storage compression schemes can be derived.Furthermore, local enumeration and storage techniques are shown to be orthogonal, if the local storage compression scheme is collapsible.Performance figures of the methods are given for a number of different processors.

Data parallel languages, like High Performance Fortran (HPF), support the notion of distributed arrays. However, the implementation of such distributed array structures and their access on message passing computers is not straightforward. This holds especially for distributed arrays that are aligned to each other and given a block-cyclic distribution. In this paper, an implementation framework is presented for HPF distributed arrays on message passing computers. Methods are presented for efficient (in space and time) local index enumeration, local storage, and communication. Techniques for local set enumeration provide the basis for constructing local iteration sets and communication sets. It is shown that both local set enumeration and local storage schemes can be derived from the same equation. Local set enumeration and local storage schemes are shown to be orthogonal, i.e., they can be freely combined. Moreover, for linear access sequences generated by our enumeration methods, the local address calculations can be moved out of the enumeration loop, yielding efficient local memory address generation. The local set enumeration methods are implemented by using a relatively simple general transformation rule for absorbing ownership tests. This transformation rule can be repeatedly applied to absorb multiple ownership tests. Performance figures are presented for local iteration overhead, a simple communication pattern, and storage efficiency.

An integrated approach for the parallel solution of large sparse systems arisen in finite element computations is presented. The approach includes a three-phase preprocessor and a macro dataflow execution scheme. The three phases of the preprocessor are: (1) Extracting parallelism by means of an automatic domain decomposer; (2) Building the distributed data structure and (partial) scheduling for parallel computation during symbolic factorization; (3) Assigning processes (tasks) onto processors. The proposed approach has been implemented in the finite element analysis software package DIANA. Experimental results show that this integrated approach is an efficient method for both shared-and distributed-memory parallel systems.

A pipelined vector-reduction method that is based on L.M. Ni and K. Hwang's (1985) symmetric and asymmetric reduction methods is discussed. It is shown that the proposed method is the fastest among known pipelined vector-reduction methods.>

This paper describes a translation method for the automatic parallelization of programs based on a separately specified representation of the data. The method unifies the concept of data-representation on the algorithm-level as well as machine-level, based on the so-called view concept. It is shown that given a decomposition of the data, application of the translation method to the view-based Booster programming language results in efficient SPMD-code for distributed- as well as shared-memory architectures. It will be argued that the method is not restricted to Booster, but can also be applied to other languages.

A number of new algorithms to make an online CORDIC implementation are introduced. The online CORDIC algorithm takes n+6 clock cycles to compute a CORDIC function. It is estimated that an implementation of the proposed algorithm is six to seven times as fast as the traditional CORDIC approach for Given's rotation, and seven to eight times as fast for SVD computation.>

The CORDIC algorithms provide a fast way to calculate a number of basic arithmetic functions. A CORDIC calculation takes O(n) steps for a function, where n is the word length of the operands. The speed is limited by the carry propagation in the adders and the I/O throughput. Speed can be improved by introducing redundancy in the calculation circuitry and I/O throughput by doing I/O transfers while calculating. The latter is characteristic for the class of so-called online arithmetic. At the same time, the pin requirements are limited to a single digit per operand. The authors introduce a number of new algorithms that provide an online CORDIC implementation.>

This paper describes a new online division (reciprocal) algorithm for (maximally) redundant floating-point numbers of arbitrary radix. The algorithm works for normalized, quasi-normalized, and pseudo-normailized numbers and can therefore be applied in chained online compuatations. The online delay of die proposed algorithm is the smallest reported so far. The algorithm consista of two steps: the first m digits of the result are generated by a simple table lookup method; the remaining n-m digits are generated by using an adapted Newton-Raphson iteration method. In the second step, the online digits are created by using a fast and simple selection mechanism.

A bit-sequential processing element with O(n) complexity is described, where n is the wordlength of the operands. The operations performed by the element are A * B + C * D, A/B, and √A. The operands are fixed point or floating point numbers with variable precision. The concept of semi-on-line algorithms is introduced. A processing element that uses semi-on-line algorithms produces a result δ clock cycles after the absorption of the n-bit operands, where δ is small compared to n. In the paper the processing element and the algorithms are described. A performance comparison between the bit-sequential processing element and conventional pipelined arithmetic units is given.

For the realization of a bit-sequential multiplier with operands of length n, Chen and Willoner1 suggest a circuitry consisting of 2n identical modules. It is shown that if a slightly different arrangement of the modules is taken, the number of modules is reduced to n. Furthermore, the implementation in circuit form can be made more simple.