| 161. |
- Månsson, Tommie, 1987, et al.
(författare)
-
Analysis of door openings of refrigerated display cabinets in an operational supermarket
- 2019
-
Ingår i: Journal of Building Engineering. - : Elsevier BV. - 2352-7102. ; 26:Nov.
-
Tidskriftsartikel (refereegranskat)abstract
- This article presents a suite of data sets describing door openings of refrigerated display cabinets collected from an operational supermarket. Our goal is to provide a realistic and well-documented suite that will serve as a basis for consistent evaluation and study. Many applications ranging from modelling and optimising supermarket refrigeration systems to food safety and customer modelling depend on such data sets. We describe the data sets in the suite in detail along with the methodology used to collect them from an operational supermarket in Germany. We quantitatively analyse and characterise a total of openings reported in the data sets. The properties that we study are opening speed, frequency, time, duration and opening angle with respect to a given weekday, time and type of refrigerator. We expect the current suite of data sets to attract interest and to become the core of a more extensive collection of data sets with time.
|
|
| 162. |
- Najdataei, Hannaneh, 1988, et al.
(författare)
-
pi-Lisco: parallel and incremental stream-based point-cloud clustering
- 2022
-
Ingår i: Proceedings of the ACM Symposium on Applied Computing. - New York, NY, USA : ACM. ; , s. 460-469
-
Konferensbidrag (refereegranskat)abstract
- Point-cloud clustering is a key task in applications like autonomous vehicles and digital twins, where rotating LiDAR sensors commonly generate point-cloud measurements in data streams. The state-of-the-art algorithms, Lisco and its parallel equivalent P-Lisco, define a single-pass distance-based clustering. However, while outperforming other batch-based techniques, they cannot incrementally cluster point-clouds from consecutive LiDAR rotations, as they cannot exploit result-similarity between rotations. The simplicity of Lisco, along with the potential of improvements through utilization of computational overlaps, form the motivation of a more challenging objective studied here. We propose Parallel and Incremental Lisco (pi-Lisco), which, with a simple yet efficient approach, clusters LiDAR data in streaming sliding windows, reusing the results from overlapping portions of the data, thus, enabling single-window (i.e., in-place) processing. Moreover, pi-Lisco employs efficient work-sharing among threads, facilitated by the ScaleGate data structure, and embeds a customised version of the STINGER concurrent data structure. Through an orchestration of these key ideas, pi-Lisco is able to lead to significant performance improvements. We complement with an evaluation of pi-Lisco, using the Ford Campus real-world extensive data-set, showing (i) the computational benefits from incrementally processing the consecutive point-clouds; and (ii) the fact that pi-Lisco' parallelization leads to continuously increasing sustainable rates with increasing number of threads, shifting the saturation point of the baseline.
|
|
| 163. |
- Najdataei, Hannaneh, 1988, et al.
(författare)
-
STRETCH: Scalable and elastic deterministic streaming analysis with virtual shared-nothing parallelism
- 2019
-
Ingår i: DEBS 2019 - Proceedings of the 13th ACM International Conference on Distributed and Event-Based Systems. - New York, NY, USA : ACM. ; , s. 7-18
-
Konferensbidrag (refereegranskat)abstract
- Despite the established scientific knowledge on efficient parallel and elastic data stream processing, it is challenging to combine generality and high level of abstraction (targeting ease of use) with fine-grained processing aspects (targeting efficiency) in stream processing frameworks. Towards this goal, we propose STRETCH, a framework that aims at guaranteeing (i) high efficiency in throughput and latency of stateful analysis and (ii) fast elastic reconfigurations (without requiring state transfer) for intra-node streaming applications. To achieve these, we introduce virtual shared-nothing parallelization and propose a scheme to implement it in STRETCH, enabling users to leverage parallelization techniques while also taking advantage of shared-memory synchronization, which has been proven to boost the scaling-up of streaming applications while supporting determinism. We provide a fully-implemented prototype and, together with a thorough evaluation, correctness proofs for its underlying claims supporting determinism and a model (also validated empirically) of virtual shared-nothing and pure shared-nothing scalability behavior. As we show, STRETCH can match the throughput and latency figures of the front of state-of-the-art solutions, while also achieving fast elastic reconfigurations (taking only a few milliseconds).
|
|
| 164. |
- Nguyen, Dang Nhan, 1983, et al.
(författare)
-
Brief Announcement: ParMarkSplit: A Parallel Mark-Split Garbage Collector Based on a Lock-Free Skip-List
- 2013
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - : Springer. - 1611-3349 .- 0302-9743. - 9783642415265 ; 8205, s. 557-558
-
Konferensbidrag (refereegranskat)abstract
- This brief announcement provides a high level overview of a parallel mark-split garbage collector. Our parallel design introduces and makes use of an efficient concurrency control mechanism based on a lock-free skip-list design for handling the list of free memory intervals. We have implemented the parallel mark-split garbage collector in OpenJDK HotSpot as a parallel and concurrent garbage collector for the old generation. We experimentally evaluate the collector and compare it with the default concurrent mark-sweep garbage collector in OpenJDK HotSpot, using the DaCapo benchmarks.
|
|
| 165. |
- Nguyen, Dang Nhan, 1983, et al.
(författare)
-
CoMarkSplit: A Concurrent Mark-Split Garbage Collector
- 2012
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Garbage collectors are important components of many modern programming languages and runtime systems. Mark-split is a garbage collection algorithm that combines advantages of both mark-sweep and copying collection algorithms. With the switch to multi-core and many-core microprocessors, parallelism becomes a core issue in the design of any algorithm or software system. In this paper, we present a concurrent design of the mark-split garbage collector. Our concurrent design algorithmically introduces and makes use of an efficient concurrency control mechanism for handling the list of free intervals. This mechanism is based on a lock-free skip-list design and supports an extended set of operations that allows, atomically and in a lock-free manner, to search and remove and also to insert two intervals at the same time. We have implemented the concurrent mark-split garbage collector in OpenJDK HotSpot as a garbage collector for the tenured generation. We present experimental evaluation of our concurrent collector and compare it with the default concurrent marks-sweep garbage collector present in OpenJDK HotSpot, using the Dacapo benchmarks. The evaluation shows that our concurrent mark-split performs better than the concurrent mark-sweep garbage collector in some applications.
|
|
| 166. |
- Nguyen, Dang Nhan, 1983, et al.
(författare)
-
Lock-free Cuckoo Hashing
- 2014
-
Ingår i: The 34th International Conference on Distributed Computing Systems (ICDCS). - 9781479951680 ; , s. 627-636
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a lock-free cuckoo hashing algorithm; to the best of our knowledge this is the first lock-free cuckoo hashing in the literature. The algorithm allows mutating operations to operate concurrently with query ones and requires only single word compare-and-swap primitives. Query of items can operate concurrently with others mutating operations, thanks to the two-round query protocol enhancedwith a logical clock technique. When an insertion triggers asequence of key displacements, instead of locking the wholecuckoo path, our algorithm breaks down the chain of relocations into several single relocations which can be executed independently and concurrently with other operations. A fine tuned synchronization and a helping mechanism for relocation are designed. The mechanisms allow high concurrency and provide progress guarantees for the data structure’s operations. Our experimental results show that our lock-free cuckoo hashing performs consistently better than two efficient lock-based hashing algorithms, the chained and the hopscotch hash map, in different access pattern scenarios.
|
|
| 167. |
- Nguyen, Dang Nhan, 1983, et al.
(författare)
-
ParMarkSplit : A Parallel Mark-Split Garbage Collector Based on a Lock-Free Skip-List
- 2014
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer. - 1611-3349 .- 0302-9743. - 9783319144719 - 9783319144726 ; 8878, s. 372-387
-
Konferensbidrag (refereegranskat)abstract
- Mark-split is a garbage collection algorithm that combines advantages of both the mark-sweep and the copying collection algorithms. In this paper, we present a parallel mark-split garbage collector (GC). Our parallel design introduces and makes use of an efficient concurrency control mechanism for handling the list of free memory intervals. This mechanism is based on a lock-free skip-list design which supports an extended set of operations. Beside basic operations, it can perform a composite one that can search and remove and also insert two elements atomically. We have implemented the parallel mark-split GC in OpenJDK’s HotSpot virtual machine. We experimentally evaluate our collector and compare it with the default concurrent mark-sweep GC in HotSpot, using the DaCapo benchmarks, on two contemporary multiprocessor systems; one has 12 Intel Nehalem cores with HyperThreading and the other has 48 AMD Bulldozer cores. The evaluation shows that our parallel mark-split keeps the characteristics of the sequential mark-split, that it performs better than the concurrent mark-sweep in applications that have low live/garbage ratio, and have live objects locating contiguously, therefore being marked consecutively. Our parallel mark-split performs significantly better than a trivial parallelization based on locks in terms of both collection time and scalability.
|
|
| 168. |
- Nguyen, Dang Nhan, 1983, et al.
(författare)
-
Progress guarantees when composing lock-free objects
- 2011
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - 1611-3349 .- 0302-9743. - 9783642233968 ; Part II, s. 148--159-
-
Konferensbidrag (refereegranskat)abstract
- Highly concurrent and reliable data objects are vital for parallel programming. Lock-free shared data objects are highly concurrent and guarantee that at least one operation, from a set of concurrently executed operations, finishes after a finite number of steps regardless of the state of the other operations. Lock-free data objects provide progress guarantees on the object level. In this paper, we first examine the progress guarantees provided by lock-free shared data objects that have been constructed by composing other lock-free data objects. We observe that although lock-free data objects are composable when it comes to linearizability, when it comes to progress guarantees they are not. More specifically we show that when a lock-free data object is used as a component (is shared) by two or more lock-free data objects concurrently, these objects can no longer guarantee lock-free progress. This makes it impossible for programmers to directly compose lock-free data objects and guarantee lock-freedom. To help programmability in concurrent settings, this paper presents a new synchronization mechanism for composing lock-free data objects. The proposed synchronization mechanism provides an interface to be used when calling a lock-free object from other lock-free objects, and guarantees lock-free progress for every object constructed. An experimental evaluation of the performance cost that the new mechanism introduces, as expected, for providing progress guarantees is also presented.
|
|
| 169. |
- Nikolakopoulos, Ioannis, 1986, et al.
(författare)
-
A Consistency Framework for Iteration Operations in Concurrent Data Structures
- 2015
-
Ingår i: 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, May 25-29, 2015. - : IEEE Computer Society. - 1530-2075. - 9781479986484 ; , s. 239-248
-
Konferensbidrag (refereegranskat)abstract
- Concurrent data structures provide the means to multi-threaded applications to share data. Data structures come with a set of predefined operations, specified by the semantics of the data structure. In the literature and in several contemporary commonly used programming environments, the notion of iteration has been introduced for collection data structures, as a bulk operation enhancing the native set of operations. Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures. In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide. Besides invariability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamppost's systematic definitions for registers. Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations. Besides the trade-off between consistency and throughput, we point out and study trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure.
|
|
| 170. |
- Nikolakopoulos, Ioannis, 1986, et al.
(författare)
-
Enhancing Concurrent Data Structures with Concurrent Iteration Operations
- 2014
-
Ingår i: MCC14: Seventh Swedish Workshop on Multicore Computing.
-
Konferensbidrag (refereegranskat)abstract
- Concurrent data structures provide the means to multi-threaded applications to share data.Data structures come with a set of predefined operations, specified by the semantics of the data structure.In the literature and in several contemporary commonly used programming environments,the notion of iteration has been introduced for collection data structures,as a bulk operation enhancing the native set of operations.Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures.In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide.Besides linearizability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamport's systematic definitions for registers.Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations.Besides the trade-off between consistency and throughput, we demonstrate the trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure. We describe a set of algorithms that demonstrate these and study the implications on the efficiency of the implementations.
|
|
