Wyniki wyszukiwania - BazTech

1

Resolving classical concurrency problems using outlier detection

Smoliński M.

Journal of Applied Computer Science

|

2017

|

Vol. 25, nr 2

69--88

EN

In this paper outlier detection is used to determine anomaly between tasks to prevent occurrence of resource conflicts in prepared schedule. Determined conflictless schedule bases on controlling access of tasks to groups of shared resources. Proposed approach allows to prepare conflictless schedule of effcient parallel task processing without resource conflicts and is dedicated to environments of task processing with high contention of shared resources. In this paper the outlier detection is used to resolve two classical concurrency problems: readers and writers and dining philosophers. In opposition to other known solutions of concurrency problems, proposed approach can be applied to solve different problems and do not require to use additional mechanisms of task synchronization. The universality of proposed approach allows to prepare conflictless schedule even in environments, where classical concurrency problems will be significantly expanded and complicated.

2

The GPU performance in coordination of parallel tasks in access to resource groups without conflicts

Smoliński M.

Information Systems in Management

|

2017

|

Vol. 6, No. 2

143--153

EN

In high contention environments, with limited number of shared resources, elimination of resource conflicts between tasks processed in parallel is required. Execution of all tasks without resource conflicts can be achieved by preparing a proper overall schedule for all of them. The effective calculation of conflict-free execution plan for tasks provides the conflictless scheduling algorithm that is dedicated to GPU massively parallel processing. The conflictless scheduling algorithm base on rapid resource conflict detection to mutual exclusion of conflicted tasks in access to global resources and is an alternative to other task synchronization methods. This article presents the performance of modern GPU in calculations of adaptive conflictless task schedule. The performance analysis also takes into account all data transfers to and from the GPU memory in various phases of the conflictless task scheduling algorithm.

3

Invariant Structures and Dependence Relations

Janicki R., Kleijn J., Koutny M., Mikulski Ł.

Fundamenta Informaticae

|

2017

|

Vol. 155, nr 1/2

1--29

EN

A step trace is an equivalence class of step sequences which can be thought of as different observations of the same underlying concurrent history. Equivalence is determined on basis of a step alphabet that describes the relations between events in terms of potential simultaneity and sequentialisability. Step traces cannot be represented by standard partial orders, but require so-called invariant structures, extended order structures that capture the phenomena of mutual exclusion and weak causality. In this paper, we present an effective way of deciding whether an invariant structure represents a step trace over a given step alphabet. We also describe a method by which one can check whether a given invariant structure can represent a step trace over any step alphabet. Moreover, if the answer is positive, the method provides a suitable step alphabet.

4

Alphabets of Acyclic Invariant Structures

Janicki R., Kleijn J., Koutny M., Mikulski Ł.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

207--224

EN

A step trace is an equivalence class of step sequences, where the equivalence is determined by dependencies between pairs of actions expressed as potential simultaneity and sequentialisability. Step traces can be represented by invariant structures with two relations: mutual exclusion and (possibly cyclic) weak causality. An important issue concerning invariant structures is to decide whether an invariant structure represents a step trace over a given step alphabet. For the general case this problem has been solved and an effective decision procedure has been proposed. In this paper, we restrict the class of order structures being considered with the aim of achieving a better characterisation. Requiring that the weak causality relation is acyclic, makes it possible to solve the problem in a purely local way, by considering pairs of events, rather than whole structures.

5

Elimination of task starvation in conflictless scheduling concept

Smoliński M.

Information Systems in Management

|

2016

|

Vol. 5, No. 2

237--247

EN

New concept of conflictless task scheduling is an alternative approach to existing solutions in concurrency. Conflictless task scheduling includes data structures and algorithm that prevents occurrence of resource conflict between tasks executed in parallel. The range of applications the conflictless task scheduling includes different environments like transactions processing in database management systems, scheduling of processes or threads in operating systems or business processes management. Task scheduling without any resource conflicts is dedicated to high contention of limited resources environments and its algorithm can be implemented in modern GPU. This paper presents concept of local task scheduling without resources conflicts occurrence, discusses features of new approach and focuses on problem of task starvation. Elimination of task starvation is included in conflictless task scheduling concept, detailed explanation are contained in this paper.

6

Generalized Mutual Exclusion with semaphores only

Ordman E.T., Eberbach E., Anwar A.

Fundamenta Informaticae

|

1999

|

Vol. 40, Nr 4

407-422

EN

The paper deals with a generic solution of the Mutual Exclusion Problem using semaphores only. We use in the solution weakly fair binary semaphores and (not necessarily fair) semaphores with initial value k. All semaphores are simple in that the P and V operations on them are paired in the natural way avoiding split semaphores. No auxiliary shared variables are used. We define a general form of the mutual exclusion problem. We claim: (1) All mutual exclusion problems can be solved using only simple semaphores. (2) All mutual exclusion problems can be solved fairly (with bounded waiting) using simple semaphores (weakly fair binary and initially-k semaphores). We give some bounds on how many semaphores are needed for standard problems. The solutions given may be inefficient: a mutual exclusion problem which can be solved in linear time and space with shared variables may require exponentially many semaphores.