Search

The OpenMP specification lacks a composable shared memory concurrency mechanism: the current OpenMP concurrency mechanisms, such as OMP critical, locks, or atomics, do not support composition. In this paper, we motivate the need for transactional memory (TM) in OpenMP. The chief reason is to support composition of realistic programs, but we also consider whether TM is easier to program than locks, the use case for TM, and whether a software-only TM can outperform traditional locking through a survey of recent publications. This paper advances upon previous proposals of OpenMP TM by introducing a new construct specifically to handle irrevocable actions, which is also composable. It also proposes a pure atomic transaction construct as well as the concept of transaction safety. Further, we examine how our proposed construct integrates with current OpenMP constructs.

We study problems that arise in the context of covering certain geometric objects called seeds (e.g., points or disks) by a set of other geometric objects called cover (e.g., a set of disks or homothetic triangles). We insist that the interiors of the seeds and the cover elements are pairwise disjoint, respectively, but they can touch. We call the contact graph of a cover a cover contact graph (CCG). We are interested in three types of tasks, both in the general case and in the special case of seeds on a line: (a) deciding whether a given seed set has a connected CCG, (b) deciding whether a given graph has a realization as a CCG on a given seed set, and (c) bounding the sizes of certain classes of CCG's. Concerning (a) we give efficient algorithms for the case that seeds are points and show that the problem becomes hard if seeds and covers are disks. Concerning (b) we show that this problem is hard even for point seeds and disk covers (given a fixed correspondence between graph vertices and seeds). Concerning (c) we obtain upper and lower bounds on the number of CCG's for point seeds., Journal of Computational Geometry, Vol. 3 No. 1 (2012)

Shannon’s entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based compression. A plausible lower bound is b, the least number of phrases of a general bidirectional parse of a text, where phrases can be copied from anywhere else in the text. Since computing b is NP-complete, a popular gold standard is z, the number of phrases in the Lempel-Ziv parse of the text, where phrases can be copied only from the left. While z can be computed in linear time, almost nothing has been known for decades about its approximation ratio with respect to b. In this paper we prove that $$z=O(b\log (n/b))$$ z = O ( b log ( n / b ) ) , where n is the text length. We also show that the bound is tight as a function of n, by exhibiting a string family where $$z = \varOmega (b\log n)$$ z = Ω ( b log n ) . Our upper bound is obtained by building a run-length context-free grammar based on a locally consistent parsing of the text. Our lower bound is obtained by relating b with r, the number of equal-letter runs in the Burrows-Wheeler transform of the text. On our way, we prove other relevant bounds between compressibility measures.

The increasing size of container vessels is raising the complexity of daily operations of both the carrier and the terminal. This paper focuses on stowage planning, the problem of assigning container to positions in a vessel. In particular, it studies the implementation of known planning strategies within an optimisation framework. Block stowage and crane intensity are presented and mathematically modelled on a simplified version of the problem. An experimental evaluation, on a large set of novel benchmark instances, shows that even in this simplified version the problem is not trivially solved. A matheuristic based on large neighbourhood search is presented, which is able to find a solution to all instances in short computational times.

Heterogeneous systems are an important trend in the future of supercomputers, yet they can be hard to program and developers still lack powerful tools to gain understanding about how well their accelerated codes perform and how to improve them. Having different types of hardware accelerators available, each with their own specific low-level APIs to program them, there is not yet a clear consensus on a standard way to retrieve information about the accelerator’s performance. To improve this scenario, OMPT is a novel performance monitoring interface that is being considered for integration into the OpenMP standard. OMPT allows analysis tools to monitor the execution of parallel OpenMP applications by providing detailed information about the activity of the runtime through a standard API. For accelerated devices, OMPT also facilitates the exchange of performance information between the runtime and the analysis tool. We implement part of the OMPT specification that refers to the use of accelerators both in the Nanos++ parallel runtime system and the Extrae tracing framework, obtaining detailed performance information about the execution of the tasks issued to the accelerated devices to later conduct insightful analysis. Our work extends previous efforts in the field to expose detailed information from the OpenMP and OmpSs runtimes, regarding the activity and performance of task-based parallel applications. In this paper, we focus on the evaluation of FPGA devices studying the performance of two common kernels in scientific algorithms: matrix multiplication and Cholesky decomposition. Furthermore, this development is seamlessly applicable for the analysis of GPGPU accelerators and Intel®Xeon PhiTM co-processors operating under the OmpSs programming model. This work was partially supported by the European Union H2020 program through the AXIOM project (grant ICT-01-2014 GA 645496) and the Mont-Blanc 2 project, by the Ministerio de Economía y Competitividad, under contracts Computación de Altas Prestaciones VII (TIN2015-65316-P); Departament d'Innovació, Universitats i Empresa de la Generalitat de Catalunya, under projects MPEXPAR: Models de Programació i Entorns d'Execució Paral·lels (2014-SGR-1051) and 2009-SGR-980; the BSC-CNS Severo Ochoa program (SEV-2011-00067); the Intel-BSC Exascale Laboratory project; and the OMPT Working Group.

© 2014 Springer International Publishing Switzerland. OmpSs is a task-based programming model that aims to provide portability and flexibility for sequential codes while the performance is achieved by the dynamic exploitation of the parallelism at task level. OmpSs targets the programming of heterogeneous and multi-core architectures and offers asynchronous parallelism in the execution of the tasks. The main extension of OmpSs, now incorporated in the recent OpenMP 4.0 standard, is the concept of data dependences between tasks. Tasks in OmpSs are annotated with data directionality clauses that specify the data used by it, and how it will be used (read, write or read&write). This information is used during the execution by the underlying OmpSs runtime to control the synchronization of the different instances of tasks by creating a dependence graph that guarantees the proper order of execution. This mechanism provides a simple way to express the order in which tasks must be executed, without the need of adding explicit synchronization. Additionally, OmpSs syntax offers the flexibility to express that given tasks can be executed on heterogeneous target architectures (i.e., regular processors, GPUs, or FPGAs). The runtime is able to schedule and run these tasks, taking care of the required data transfers and synchronizations. OmpSs is a promising programming model for future exascale systems, with the potential to exploit unprecedented amounts of parallelism while coping with memory latency, network latency and load imbalance. The paper covers the basics of OmpSs and some recent new developments to support a family of embedded DSLs (eDSLs) on top of the compiler and runtime, including an prototype implementation of a Partial Differential Equations DSL.

Further results of research into graph grammar-based parsing for syntactic pattern recognition (Pattern Recognition: 21, 623-629 (1988); 23, 765-774 (1990); 26, 1-16 (1993); 43, 2249-2264 (2010), Comput. Vision Graph. Image Process. 47, 1-21 (1989), Theoret. Comp. Sci. 201, 189-231 (1998)) are presented in the paper. The bottom-up parsable ETPR(k) subclass of well-known edNLC graph grammars is defined.

In this paper, we consider the extension of multi-objective constraint optimization algorithms to the case where there are additional tradeoffs, reducing the number of optimal solutions. We focus especially on branch-and-bound algorithms which use a mini-buckets algorithm for generating the upper bound at each node (in the context of maximizing values of objectives). Since the main bottleneck of these algorithms is the very large size of the guiding upper bound sets we introduce efficient methods for reducing these sets, yet still maintaining the upper bound property. We also propose much faster dominance checks with respect to the preference relation induced by the tradeoffs. Furthermore, we show that our tradeoffs approach which is based on a preference inference technique can also be given an alternative semantics based on the well known Multi-Attribute Utility Theory. Our comprehensive experimental results on common multi-objective constraint optimization benchmarks demonstrate that the proposed enhancements allow the algorithms to scale up to much larger problems than before.

Comunicació presentada a: PKC 2010. 13th International Conference on Practice and Theory in Public Key Cryptography, celebrada del 26 al 28 de maig de 2010 a París, França. Attribute-based cryptography has emerged in the last years as a promising primitive for digital security. For instance, it provides good solutions to the problem of anonymous access control. In a ciphertext- policy attribute-based encryption scheme, the secret keys of the users de- pend on their attributes. When encrypting a message, the sender chooses which subset of attributes must be held by a receiver in order to be able to decrypt. All current attribute-based encryption schemes that admit reasonably expressive decryption policies produce ciphertexts whose size depends at least linearly on the number of attributes involved in the policy. In this paper we propose the first scheme whose ciphertexts have constant size. Our scheme works for the threshold case: users authorized to decrypt are those who hold at least t attributes among a certain universe of attributes, for some threshold t chosen by the sender. An extension to the case of weighted threshold decryption policies is possible. The security of the scheme against selective chosen plaintext attacks can be proven in the standard model by reduction to the augmented multi-sequence of exponents decisional Di e-Hellman (aMSE-DDH) problem. The work of Javier Herranz is supported by a Ramón y Cajal grant, partially funded by the European Social Fund (ESF) of the Spanish MICINN Ministry. Carla Ràfols holds an FPI grant of the Spanish MICINN Ministry. The work of both these authors is partially supported by the Spanish MICINN Ministry under project MTM2009-07694. The work of Fabien Laguillaumie is supported by the French ANR-07-TCOM-013-04 PACE Project.

Performance analysis is very important to understand the applications’ behavior and to identify bottlenecks. Performance analysis tools should facilitate the exploration of the data collected and help to identify where the analyst has to look. While this functionality can promote the tools usage on small and medium size environments, it becomes mandatory for large-scale and many-core systems where the amount of data is dramatically increased. This paper proposes a new methodology based on the integration of profilers and timeline tools to improve and facilitate the performance analysis process.