| 1. |
- Chatterjee, Bapi, 1982
(författare)
-
Lock-free Concurrent Search
- 2017
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The contemporary computers typically consist of multiple computing cores with high compute power. Such computers make excellent concurrent asynchronous shared memory system. On the other hand, though many celebrated books on data structure and algorithm provide a comprehensive study of sequential search data structures, unfortunately, we do not have such a luxury if concurrency comes in the setting. The present dissertation aims to address this paucity. We describe novel lock-free algorithms for concurrent data structures that target a variety of search problems. (i) Point search (membership query, predecessor query, nearest neighbour query) for 1-dimensional data: Lock-free linked-list; lock-free internal and external binary search trees (BST). (ii) Range search for 1-dimensional data: A range search method for lock-free ordered set data structures - linked-list, skip-list and BST. (iii) Point search for multi-dimensional data: Lock-free kD-tree, specially, a generic method for nearest neighbour search. We prove that the presented algorithms are linearizable i.e. the concurrent data structure operations intuitively display their sequential behaviour to an observer of the concurrent system. The lock-freedom in the introduced algorithms guarantee overall progress in an asynchronous shared memory system. We present the amortized analysis of lock-free data structures to show their efficiency. Moreover, we provide sample implementations of the algorithms and test them over extensive micro-benchmarks. Our experiments demonstrate that the implementations are scalable and perform well when compared to related existing alternative implementations on common multi-core computers. Our focus is on propounding the generic methodologies for efficient lock-free concurrent search. In this direction, we present the notion of help-optimality, which captures the optimization of amortized step complexity of the operations. In addition to that, we explore the language-portable design of lock-free data structures that aims to simplify an implementation from programmer’s point of view. Finally, our techniques to implement lock-free linearizable range search and nearest neighbour search are independent of the underlying data structures and thus are adaptive to similar data structures.
|
|
| 2. |
- Nilsson, R. Henrik, 1976, et al.
(författare)
-
Mycobiome diversity: high-throughput sequencing and identification of fungi.
- 2019
-
Ingår i: Nature reviews. Microbiology. - : Springer Science and Business Media LLC. - 1740-1534 .- 1740-1526. ; 17, s. 95-109
-
Forskningsöversikt (refereegranskat)abstract
- Fungi are major ecological players in both terrestrial and aquatic environments by cycling organic matter and channelling nutrients across trophic levels. High-throughput sequencing (HTS) studies of fungal communities are redrawing the map of the fungal kingdom by hinting at its enormous - and largely uncharted - taxonomic and functional diversity. However, HTS approaches come with a range of pitfalls and potential biases, cautioning against unwary application and interpretation of HTS technologies and results. In this Review, we provide an overview and practical recommendations for aspects of HTS studies ranging from sampling and laboratory practices to data processing and analysis. We also discuss upcoming trends and techniques in the field and summarize recent and noteworthy results from HTS studies targeting fungal communities and guilds. Our Review highlights the need for reproducibility and public data availability in the study of fungal communities. If the associated challenges and conceptual barriers are overcome, HTS offers immense possibilities in mycology and elsewhere.
|
|
| 3. |
- Abbas, Nadeem, 1980-, et al.
(författare)
-
ASPLe : a methodology to develop self-adaptive software systems with reuse
- 2017
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Advances in computing technologies are pushing software systems and their operating environments to become more dynamic and complex. The growing complexity of software systems coupled with uncertainties induced by runtime variations leads to challenges in software analysis and design. Self-Adaptive Software Systems (SASS) have been proposed as a solution to address design time complexity and uncertainty by adapting software systems at runtime. A vast body of knowledge on engineering self-adaptive software systems has been established. However, to the best of our knowledge, no or little work has considered systematic reuse of this knowledge. To that end, this study contributes an Autonomic Software Product Lines engineering (ASPLe) methodology. The ASPLe is based on a multi-product lines strategy which leverages systematic reuse through separation of application and adaptation logic. It provides developers with repeatable process support to design and develop self-adaptive software systems with reuse across several application domains. The methodology is composed of three core processes, and each process is organized for requirements, design, implementation, and testing activities. To exemplify and demonstrate the use of the ASPLe methodology, three application domains are used as running examples throughout the report.
|
|
| 4. |
- Abbas, Nadeem, 1980-
(författare)
-
Designing Self-Adaptive Software Systems with Reuse
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Modern software systems are increasingly more connected, pervasive, and dynamic, as such, they are subject to more runtime variations than legacy systems. Runtime variations affect system properties, such as performance and availability. The variations are difficult to anticipate and thus mitigate in the system design.Self-adaptive software systems were proposed as a solution to monitor and adapt systems in response to runtime variations. Research has established a vast body of knowledge on engineering self-adaptive systems. However, there is a lack of systematic process support that leverages such engineering knowledge and provides for systematic reuse for self-adaptive systems development. This thesis proposes the Autonomic Software Product Lines (ASPL), which is a strategy for developing self-adaptive software systems with systematic reuse. The strategy exploits the separation of a managed and a managing subsystem and describes three steps that transform and integrate a domain-independent managing system platform into a domain-specific software product line for self-adaptive software systems.Applying the ASPL strategy is however not straightforward as it involves challenges related to variability and uncertainty. We analyzed variability and uncertainty to understand their causes and effects. Based on the results, we developed the Autonomic Software Product Lines engineering (ASPLe) methodology, which provides process support for the ASPL strategy. The ASPLe has three processes, 1) ASPL Domain Engineering, 2) Specialization and 3) Integration. Each process maps to one of the steps in the ASPL strategy and defines roles, work-products, activities, and workflows for requirements, design, implementation, and testing. The focus of this thesis is on requirements and design.We validate the ASPLe through demonstration and evaluation. We developed three demonstrator product lines using the ASPLe. We also conducted an extensive case study to evaluate key design activities in the ASPLe with experiments, questionnaires, and interviews. The results show a statistically significant increase in quality and reuse levels for self-adaptive software systems designed using the ASPLe compared to current engineering practices.
|
|
| 5. |
- Mallozzi, Piergiuseppe, 1990, et al.
(författare)
-
A runtime monitoring framework to enforce invariants on reinforcement learning agents exploring complex environments
- 2019
-
Ingår i: RoSE 2019, IEEE/ACM 2nd International Workshop on Robotics Software Engineering, p.5-12. - : IEEE. - 9781728122496
-
Konferensbidrag (refereegranskat)abstract
- © 2019 IEEE. Without prior knowledge of the environment, a software agent can learn to achieve a goal using machine learning. Model-free Reinforcement Learning (RL) can be used to make the agent explore the environment and learn to achieve its goal by trial and error. Discovering effective policies to achieve the goal in a complex environment is a major challenge for RL. Furthermore, in safety-critical applications, such as robotics, an unsafe action may cause catastrophic consequences in the agent or in the environment. In this paper, we present an approach that uses runtime monitoring to prevent the reinforcement learning agent to perform 'wrong' actions and to exploit prior knowledge to smartly explore the environment. Each monitor is de?ned by a property that we want to enforce to the agent and a context. The monitors are orchestrated by a meta-monitor that activates and deactivates them dynamically according to the context in which the agent is learning. We have evaluated our approach by training the agent in randomly generated learning environments. Our results show that our approach blocks the agent from performing dangerous and safety-critical actions in all the generated environments. Besides, our approach helps the agent to achieve its goal faster by providing feedback and shaping its reward during learning.
|
|
| 6. |
- Chatterjee, Bapi, 1982
(författare)
-
Efficient Implementation of Concurrent Data Structures on Multi-core and Many-core Architectures
- 2015
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Synchronization of concurrent threads is the central problem in order to design efficient concurrent data-structures. The compute systems widely available in market are increasingly becoming heterogeneous involving multi-core Central Processing Units (CPUs) and many-core Graphics Processing Units (GPUs). This thesis contributes to the research of efficient synchronization in concurrent data-structures in more than one way. It is divided into two parts. In the first part, a novel design of a Set Abstract Data Type (ADT) based on an efficient lock-free Binary Search Tree (BST) with improved amortized bounds of the time complexity of set operations - Add, Remove and Contains, is presented. In the second part, a comprehensive evaluation of concurrent Queue implementations on multi-core CPUs as well as many-core GPUs are presented. Efficient Lock-free BST -To the best of our knowledge, the lock-free BST presented in this thesis is the first to achieve an amortized complexity of O(H(n)+c) for all Set operations where H(n) is the height of a BST on n nodes and c is the contention measure. Also, the presented lock-free algorithm of BST comes with an improved disjoint-access-parallelism compared to the previously existing concurrent BST algorithms. This algorithm uses single-word compare-and-swap (CAS) primitives. The presented algorithm is linearizable. We implemented the algorithm in Java and it shows good scalability. Evaluation of concurrent data-structures - We have evaluated the performance of a number of concurrent FIFO Queue algorithms on multi-core CPUs and many-core GPUs. We studied the portability of existing design of concurrent Queues from CPUs to GPUs which are inherently designed for SIMD programs. We observed that in general concurrent queues offer them to efficient implementation on GPUs with faster cache memory and better performance support for atomic synchronization primitives such as CAS. To the best of our knowledge, this is the first attempt to evaluate a concurrent data-structure on GPUs.
|
|
| 7. |
- Aramrattana, Maytheewat, 1988-, et al.
(författare)
-
Team Halmstad Approach to Cooperative Driving in the Grand Cooperative Driving Challenge 2016
- 2018
-
Ingår i: IEEE transactions on intelligent transportation systems (Print). - Piscataway, N.J. : Institute of Electrical and Electronics Engineers Inc.. - 1524-9050 .- 1558-0016. ; 19:4, s. 1248-1261
-
Tidskriftsartikel (refereegranskat)abstract
- This paper is an experience report of team Halmstad from the participation in a competition organised by the i-GAME project, the Grand Cooperative Driving Challenge 2016. The competition was held in Helmond, The Netherlands, during the last weekend of May 2016. We give an overview of our car’s control and communication system that was developed for the competition following the requirements and specifications of the i-GAME project. In particular, we describe our implementation of cooperative adaptive cruise control, our solution to the communication and logging requirements, as well as the high level decision making support. For the actual competition we did not manage to completely reach all of the goals set out by the organizers as well as ourselves. However, this did not prevent us from outperforming the competition. Moreover, the competition allowed us to collect data for further evaluation of our solutions to cooperative driving. Thus, we discuss what we believe were the strong points of our system, and discuss post-competition evaluation of the developments that were not fully integrated into our system during competition time. © 2000-2011 IEEE.
|
|
| 8. |
- Bainomugisha, Engineer, et al.
(författare)
-
Message from Chairs of SEiA 2018
- 2018
-
Ingår i: Proceedings - International Conference on Software Engineering. - New York, NY, USA : ACM. - 0270-5257. ; 2018, s. x-xi
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)
|
|
| 9. |
- Rumman, Nadine Abu, et al.
(författare)
-
Skin deformation methods for interactive character animation
- 2017
-
Ingår i: Communications in Computer and Information Science. - Cham : Springer International Publishing. - 1865-0937 .- 1865-0929. ; 693, s. 153-174, s. 153-174
-
Konferensbidrag (refereegranskat)abstract
- Character animation is a vital component of contemporary computer games, animated feature films and virtual reality applications. The problem of creating appealing character animation can best be described by the title of the animation bible: “The Illusion of Life”. The focus is not on completing a given motion task, but more importantly on how this motion task is performed by the character. This does not necessarily require realistic behavior, but behavior that is believable. This of course includes the skin deformations when the character is moving. In this paper, we focus on the existing research in the area of skin deformation, ranging from skeleton-based deformation and volume preserving techniques to physically based skinning methods. We also summarize the recent contributions in deformable and soft body simulations for articulated characters, and discuss various geometric and example-based approaches. © Springer International Publishing AG 2017.
|
|
| 10. |
- Tuma, Katja, 1991, et al.
(författare)
-
Flaws in Flows : Unveiling Design Flaws via Information Flow Analysis
- 2019
-
Ingår i: Proceedings - 2019 IEEE International Conference on Software Architecture, ICSA 2019. - : IEEE. - 9781728105284 ; , s. 191-200
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a practical and formal approach to analyze security-centric information flow policies at the level of the design model. Specifically, we focus on data confidentiality and data integrity objectives. In its guiding principles, the approach is meant to be amenable for designers (e.g., software architects) that have very limited or no background in formal models, logics, and the like. To this aim, we provide an intuitive graphical notation, which is based on the familiar Data Flow Diagrams, and which requires as little effort as possible in terms of extra security-centric information the designer has to provide. The result of the analysis algorithm is the early discovery of design flaws in the form of violations of the intended security properties. The approach is implemented as a publicly available plugin for Eclipse and evaluated with four real-world case studies from publicly available literature.
|
|
