| 1. |
- Bauer, André, et al.
(författare)
-
Chameleon : A Hybrid, Proactive Auto-Scaling Mechanism on a Level-Playing Field
- 2019
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : IEEE Computer Society. - 1045-9219 .- 1558-2183. ; 30:4, s. 800-813
-
Tidskriftsartikel (refereegranskat)abstract
- Auto-scalers for clouds promise stable service quality at low costs when facing changing workload intensity. The major public cloud providers provide trigger-based auto-scalers based on thresholds. However, trigger-based auto-scaling has reaction times in the order of minutes. Novel auto-scalers from literature try to overcome the limitations of reactive mechanisms by employing proactive prediction methods. However, the adoption of proactive auto-scalers in production is still very low due to the high risk of relying on a single proactive method. This paper tackles the challenge of reducing this risk by proposing a new hybrid auto-scaling mechanism, called Chameleon, combining multiple different proactive methods coupled with a reactive fallback mechanism. Chameleon employs on-demand, automated time series-based forecasting methods to predict the arriving load intensity in combination with run-time service demand estimation to calculate the required resource consumption per work unit without the need for application instrumentation. We benchmark Chameleon against five different state-of-the-art proactive and reactive auto-scalers one in three different private and public cloud environments. We generate five different representative workloads each taken from different real-world system traces. Overall, Chameleon achieves the best scaling behavior based on user and elasticity performance metrics, analyzing the results from 400 hours aggregated experiment time.
|
|
| 2. |
- Carlsson, Niklas, et al.
(författare)
-
Ephemeral Content Popularity at the Edge and Implications for On-Demand Caching
- 2017
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : IEEE COMPUTER SOC. - 1045-9219 .- 1558-2183. ; 28:6, s. 1621-1634
-
Tidskriftsartikel (refereegranskat)abstract
- The ephemeral content popularity seen with many content delivery applications can make indiscriminate on-demand caching in edge networks highly inefficient, since many of the content items that are added to the cache will not be requested again from that network. In this paper, we address the problem of designing and evaluating more selective edge-network caching policies. The need for such policies is demonstrated through an analysis of a dataset recording YouTube video requests from users on an edge network over a 20-month period. We then develop a novel workload modelling approach for such applications and apply it to study the performance of alternative edge caching policies, including indiscriminate caching and cache on kth request for different k. The latter policies are found able to greatly reduce the fraction of the requested items that are inserted into the cache, at the cost of only modest increases in cache miss rate. Finally, we quantify and explore the potential room for improvement from use of other possible predictors of further requests. We find that although room for substantial improvement exists when comparing performance to that of a perfect "oracle" policy, such improvements are unlikely to be achievable in practice.
|
|
| 3. |
- Champati, Jaya Prakash, et al.
(författare)
-
Single Restart with Time Stamps for Parallel Task Processing with Known and Unknown Processors
- 2020
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : Institute of Electrical and Electronics Engineers (IEEE). - 1045-9219 .- 1558-2183. ; 31:1, s. 187-200
-
Tidskriftsartikel (refereegranskat)abstract
- We study the problem of scheduling nn tasks on m+m^{\prime }m+m' parallel processors, where the processing times on mm processors are known while those on the remaining m^{\prime }m' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with the mm known processors representing local CPU cores and the unknown processors representing remote servers with uncertain availability of computing cycles. Our objective is to minimize the makespan of all tasks. We initially focus on the case m^{\prime }=1m'=1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(n \log n)O(nlogn). We derive its competitive ratio in comparison with the optimal offline solution. If the unknown processing times are deterministic, the competitive ratio of SRTS is shown to be either always constant or asymptotically constant in practice, respectively in cases where the processing times are independent and dependent on mm. A similar result is obtained when the unknown processing times are random. Furthermore, extending the ideas of SRTS, we propose a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m^{\prime }>1m'>1. Finally, where tasks arrive dynamically with unknown arrival times, we extend SRTS to Dynamic SRTS (DSRTS) and find its competitive ratio. Besides the proven competitive ratios, simulation results further suggest that SRTS and SRTS-M give superior performance on average over randomly generated task processing times, substantially reducing the makespan over the best known alternatives. Interestingly, the performance gain is more significant for task processing times sampled from heavy-tailed distributions.
|
|
| 4. |
- Copik, Marcin, et al.
(författare)
-
Work-Stealing Prefix Scan : Addressing Load Imbalance in Large-Scale Image Registration
- 2022
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : IEEE Computer Society. - 1045-9219 .- 1558-2183. ; 33:3, s. 523-535
-
Tidskriftsartikel (refereegranskat)abstract
- Parallelism patterns (e.g., map or reduce) have proven to be effective tools for parallelizing high-performance applications. In this article, we study the recursive registration of a series of electron microscopy images - a time consuming and imbalanced computation necessary for nano-scale microscopy analysis. We show that by translating the image registration into a specific instance of the prefix scan, we can convert this seemingly sequential problem into a parallel computation that scales to over thousand of cores. We analyze a variety of scan algorithms that behave similarly for common low-compute operators and propose a novel work-stealing procedure for a hierarchical prefix scan. Our evaluation shows that by identifying a suitable and well-optimized prefix scan algorithm, we reduce time-to-solution on a series of 4,096 images spanning ten seconds of microscopy acquisition from over 10 hours to less than 3 minutes (using 1024 Intel Haswell cores), enabling derivation of material properties at nanoscale for long microscopy image series.
|
|
| 5. |
- Curescu, Calin, 1975-, et al.
(författare)
-
Time-aware Utility-based Resource Allocation in Wireless Networks
- 2005
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - 1045-9219 .- 1558-2183. ; 16:7, s. 624-635
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents a time-aware admission control and resource allocation scheme in wireless networks in the context of a future generation cellular network. The quality levels (and their respective utility) of different connections are specified using discrete resource-utility (R-U) functions. The scheme uses these R-U functions for allocating and reallocating bandwidth to connections, aiming to maximize the accumulated utility of the system. However, different applications react differently to resource reallocations. Therefore, at each allocation time point, the following factors are taken into account: the age of the connection, a disconnection (drop) penalty, and the sensitiveness to reallocation frequency. The evaluation of our approach shows a superior performance compared to a recent adaptive bandwidth allocation scheme (RBBS). In addition, we have studied the overhead that performing a reallocation imposes on the infrastructure. To minimize this overhead, we present an algorithm that efficiently reduces the number of reallocations while remaining within a given utility bound.
|
|
| 6. |
- Dán, György
(författare)
-
Cache-to-Cache : Could ISPs Cooperate to Decrease Peer-to-Peer Content Distribution Costs?
- 2011
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - 1045-9219 .- 1558-2183. ; 22:9, s. 1469-1482
-
Tidskriftsartikel (refereegranskat)abstract
- We consider whether cooperative caching may reduce the transit traffic costs of Internet service providers (ISPs) due to peer-to-peer (P2P) content distribution systems. We formulate two game-theoretic models for cooperative caching, one in which ISPs follow their selfish interests, and one in which they act altruistically. We show the existence of pure strategy Nash equilibria for both games, and evaluate the gains of cooperation on various network topologies, among them the AS level map of Northern Europe, using measured traces of P2P content popularity. We find that cooperation can lead to significant improvements of the cache efficiency with little communication overhead even if ISPs follow their selfish interests.
|
|
| 7. |
- Dán, György, et al.
(författare)
-
Delay Asymptotics and Scalability for Peer-to-Peer Live Streaming
- 2009
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : Institute of Electrical and Electronics Engineers (IEEE). - 1045-9219 .- 1558-2183. ; 20:10, s. 1499-1511
-
Tidskriftsartikel (refereegranskat)abstract
- A large number of peer-to-peer streaming systems have been proposed and deployed in recent years. Yet, there is no clear understanding of how these systems scale and how multipath and multihop transmission, properties of all recent systems, affect the quality experienced by the peers. In this paper, we present an analytical study that considers the relationship between delay and loss for general overlays: we study the trade-off between the playback delay and the probability of missing a packet and we derive bounds on the scalability of the systems. We present an exact model of push-based overlays and show that the bounds hold under diverse conditions: in the presence of errors, under node churn, and when using forward error correction and various retransmission schemes.
|
|
| 8. |
|
|
| 9. |
- Deng, Shuiguang, et al.
(författare)
-
Cost Performance Driven Service Mashup : A Developer Perspective
- 2016
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - OS ALAMITOS, CA 90720-1314 USA : IEEE Computer Society. - 1045-9219 .- 1558-2183. ; 27:8, s. 2234-2247
-
Tidskriftsartikel (refereegranskat)abstract
- Service mashups are applications created by combining single-functional services (or APIs) dispersed over the web. With the development of cloud computing and web technologies, service mashups are becoming more and more widely used and a large number of mashup platforms have been produced. However, due to the proliferation of services on the web, how to select component services to create mashups has become a challenging issue. Most developers pay more attention to the QoS (quality of service) and cost of services. Beside service selection, mashup deployment is another pivotal process, as the platform can significantly affect the quality of mashups. In this paper, we focus on creating service mashups from the perspective of developers. A genetic algorithm-based method, GA4MC (genetic algorithm for mashup creation), is proposed to select component services and deployment platforms in order to create service mashups with optimal cost performance. A series of experiments are conducted to evaluate the performance of GA4MC. The results show that the GA4MC method can achieve mashups whose cost performance is extremely close to the optimal . Moreover, the execution time of GA4MC is in a low order of magnitude and the algorithm performs good scalability as the experimental scale increases.
|
|
| 10. |
- Edelman, Alan, et al.
(författare)
-
Index Transformation Algorithms in a Linear Algebra Framework
- 1994
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : Institute of Electrical and Electronics Engineers (IEEE). - 1045-9219 .- 1558-2183. ; 5:12, s. 1302-1309
-
Tidskriftsartikel (refereegranskat)abstract
- We present a linear algebraic formulation for a class of index transformations such as Gray code encoding and decoding, matrix transpose, bit reversal, vector reversal, shuffles, and other index or dimension permutations. This formulation unifies, simplifies, and can be used to derive algorithms for hypercube multiprocessors. We show how all the widely known properties of Gray codes, and some not so well-known properties as well, can be derived using this framework. Using this framework, we relate hypercube communications algorithms to Gauss-Jordan elimination on a matrix of 0's and 1's.
|
|
