Search

International audience; We present a versatile architecture for AI-powered self-adaptive self-certifiable critical systems. It aims at supporting semi-automated low-cost re-certification for self-adaptive systems after each adaptation of their behavior to a persistent change in their operational environment throughout their lifecycle.

Recently, we developed the Parallel Heterogeneous Architecture Constraint Toolkit (PHACT), which is a multi-threaded constraint solver capable of using all the available devices which are compatible with OpenCL, in order to speed up the constraint satisfaction process. In this article, we introduce an evolution of PHACT which includes the ability to execute FlatZinc and MiniZinc models, as well as architectural improvements which boost the performance in solving CSPs, especially when using GPUs.

International audience; Many real-life applications can be formulated as Combinatorial Optimization Problems, the solution of which is often challenging due to their intrinsic difficulty. At present, the most effective methods to address the hardest problems entail the hybridization of metaheuristics and cooperative parallelism. Recently, a framework called CPLS has been proposed, which eases the cooperative parallelization of local search solvers. Being able to run different heuristics in parallel, CPLS has opened a new way to hybridize metaheuristics, thanks to its cooperative parallelism mechanism. However, CPLS is mainly designed for local search methods. In this paper we seek to overcome the current CPLS limitation, extending it to enable population-based metaheuristics in the hybridization process. We discuss an initial prototype implementation for Quadratic Assignment Problem combining a Genetic Algorithm with two local search procedures. Our experiments on hard instances of QAP show that this hybrid solver performs competitively w.r.t. dedicated QAP parallel solvers.

We propose PHYSH (Parallel HYbridization for Simple Heuristics), a framework to ease the design and implementation of hybrid metaheuristics via cooperative parallelism. With this framework, the user only needs encode each of the desired metaheuristics and may rely on PHYSH for parallelization, cooperation and hybridization. PHYSH supports the combination of population-based and single-solution metaheuristics and enables the user to control the tradeoff between intensification and diversification. We also provide an open-source implementation of this framework which we use to model the Quadratic Assignment Problem (QAP) with a hybrid solver, combining three metaheuristics. We present experimental evidence that PHYSH brings significant improvements over competing approaches, as witness the performance on representative hard instances of QAP.

International audience; Local Search metaheuristics are a recognized means of solving hard combinatorialproblems. Over the last couple of decades, significant advances have beenmade in terms of the formalization, applicability and performance of these methods.Key to the performance aspect is the increased availability of parallel hardware,which turns out to be largely exploitable by this class of procedures. As thereal-life cases of combinatorial optimisation easily degrade into intractable territoryfor exact or approximation algorithms, local search metaheuristics hold undeniableinterest. This situation is further compounded by the good adequacy exhibited bythis class of search procedures for large-scale parallel operation. In this chapter weexplore and discuss ways which lead to parallelization in Local Search.

Declarative if–then rules have proven very useful in many applications of expert systems. They can be managed in deductive databases and evaluated using the well-known forward-chaining approach. For domain-experts, however, the syntax of rules becomes complicated quickly, and already many different knowledge representation formalisms exist. Expert knowledge is often acquired in story form using interviews. In this paper, we discuss its representation by defining domain-specific languages ( Dsl s) for declarative expert rules. They can be embedded in Prolog systems in internal Dsl s using term expansion and as external Dsl s using definite clause grammars and quasi-quotations – for more sophisticated syntaxes. Based on the declarative rules and the integration with the Prolog -based deductive database system DDbase , multiple rules acquired in practical case studies can be combined, compared, graphically analysed by domain-experts, and evaluated, resulting in an extensible system for expert knowledge. As a result, the actual modeling Dsl becomes executable; the declarative forward-chaining evaluation of deductive databases can be understood by the domain experts. Our Dsl for rules can be further improved by integrating ontologies and rule annotations.

International audience; The Quadratic Assignment Problem is at the core of several real-life applications. Finding an optimal assignment is computationally very difficult, for many useful instances. The best results are obtained with hybrid heuristics, which result in complex solvers. We propose an alternate solution where hybridization is obtain by means of parallelism and cooperation between simple single-heuristic solvers. We present experimental evidence that this approach is very efficient and can effectively solve a wide variety of hard problems, often surpassing state-of-the-art systems.

International audience; Several real-life applications can be stated in terms of the Quadratic Assignment Problem. Finding an optimal assignment is com-putationally very difficult, for many useful instances. We address this problem using a local search technique, based on Extremal Optimization and present experimental evidence that this approach is competitive. Moreover, cooperative parallel versions of our solver improve performance so much that large and hard instances can be solved quickly.

We investigated the use of the Cell Broadband Engine (Cell/BE) for constraint-based local search and combinatorial optimization applications. We presented a parallel version of a constraint-based local search algorithm that was chosen because it fits very well the Cell/BE architecture because it requires neither shared memory nor communication among processors. The performance study on several large optimization benchmarks shows mostly linear time speedups, sometimes even super linear. These experiments were carried out on a dual-Cell IBM (Armonk, NY, USA) blade with 16 processors. Besides getting speedups, the execution times exhibit a much smaller variance that benefits applications where a timely reply is critical. Copyright © 2011 John Wiley & Sons, Ltd.

The boundary between the trusted inside and the untrusted outside blurs when a company adopts cloud computing. The organization's applications-and data-are no longer onsite, fundamentally changing the definition of a malicious insider.

Constraint-Based Local Search (CBLS) consist in using Local Search methods [4] for solving Constraint Satisfaction Problems (CSP). In order to further improve the performance of Local Search, one possible option is to take advantage of the increasing availability of parallel computational resources. Parallel implementation of local search meta-heuristics has been studied since the early 90's, when multiprocessor machines started to become widely available, see [6]. One usually distinguishes between single-walk and multiple-walk methods: Single-walk methods consist in using parallelism inside a single search process, e.g. for parallelizing the exploration of the neighborhood, while multiple-walk methods (also called multi-start methods) consist in developing concurrent explorations of the search space, either independently (IW) or cooperatively (CW) with some communication between concurrent processes. Although good results can be achieved just with IW [1], a more sophisticated paradigm featuring cooperation between independent walks should bring better performance. We thus propose a general framework for cooperative search, which defines a flexible and parametric strategy based on the cooperative multi-walk (CW) scheme. The framework is oriented towards distributed architectures based on clusters of nodes, with the notion of "teams" running on nodes which group several individual search engines (e.g. multicore nodes). The idea is that teams are distributed and thus have limited inter-node communication. This framework allows the programmer to define aspects such as the degree of intensification and diversification present in the parallel search process. A good trade-off is essential to reach high performance. A preliminary implementation of the general CW framework has been done in the X10 programming language [5], and performance evaluation over a set of well-known benchmark CSPs shows that CW consistently outperforms IW.

International audience; Declarative techniques such as Constraint Program- ming are very useful in modeling complex requirements. They have the added benefit of being executable specifications and, when properly tuned, high-performance ones. In this paper we argue that Information Systems ought to include constraint-based techniques in their design and imple- mentation. We support this claim by introducing tools based on constraint programming, which we apply to an actual use-case: the academic timetable construction and maintenance problem, asdevelopedattheUniversityofE ́vora.Thesystemwebuiltwas implemented using the GNU Prolog language. Moreover, Constraints have the potential to describe global properties that a model must observe, which makes them a semantically very interesting extension to the capabilities of present model-driven techniques and tools.

Constraint Programming is one approach to declarative programming where a problem is modeled as a set of variables with a domain and a set of relations constraints between them. Constraint-based Local Search builds on the idea of using constraints to describe and control local search. Problems are modeled using constraints and heuristics for which solutions are searched, using Local Search. With the progressing move toward multi and many-core systems, parallelism has become mainstream as the number of cores continues to increase. Declarative programming approaches such as those based on constraints need to be better understood and experimented in order to understand their parallel behaviour. In this paper, we discuss experiments we have been carrying out with Adaptive Search and present a new parallel version of it based on GPI, a recent API and programming model for the development of scalable parallel applications. Our experiments on different problems show interesting speed-ups and, more importantly, a better understanding of how these gains are obtained, in the context of declarative programming.

The Costas Array Problem is a highly combina- torial problem linked to radar applications. We present in this paper its detailed modeling and solving by Adaptive Search, a constraint-based local search method. Experiments have been done on both sequential and parallel hardware up to several hundreds of cores. Performance evaluation of the sequential version shows results outperforming previous implementations, while the parallel version shows nearly linear speedups up to 8,192 cores.

We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results on hard- ware with several hundreds of processors. We choose as basic constraint solving algorithm for these experiments the ”adaptive search” method, an efficient sequential local search method for Constraint Satisfaction Problems. The implemented algorithm is a parallel version of adaptive search in a multiple independent-walk manner, that is, each process is an independent search engine and there is no communication between the si- multaneous computations. Preliminary performance evaluation are very encouraging. On a variety of classical CSPs benchmarks from CSPLIB, speedups are very good for a few tens of cores, and good up to a few hundreds of processors. More challenging problems derived from real-life applications (Costas array) shows even better speedups, nearly optimal up to 256 cores.

The Costas Array Problem is a highly combinatorial problem linked to radar applications. We present in this paper its detailed modeling and solving by Adaptive Search, a constraint-based local search method. Experiments have been done on both sequential and parallel hardware up to several hundreds of cores. Performance evaluation of the sequential version shows results outperforming previous implementations, while the parallel version shows nearly linear speedups w.r.t. the sequential one, for instance 120 for 128 cores and 230 for 256 cores.

International audience; We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results on hardware with several hundreds of processors. We choose as basic constraint solving algorithm for these experiments the "adaptive search" method, an efficient sequential local search method for Constraint Satisfaction Problems. The implemented algorithm is a parallel version of adaptive search in a multiple independent-walk manner, that is, each process is an independent search engine and there is no communication between the simultaneous computations. Preliminary performance evaluation on a variety of classical CSPs benchmarks shows that speedups are very good for a few tens of processors, and good up to a few hundreds of processors.

13th International Symposium on Practical Aspects of Declarative Languages Location:Austin, TXDate:JAN 24-25, 2011, In this work we present NeMODe a declarative system for Computer Network Intrusion detection which provides a declarative Domain Specific Language for describing computer network intrusion signatures that could spread across several network packets, which allows to state constraints over network packets, describing relations between several packets, and providing several back-end detection mechanisms which relies on Constraint Programming (CP) methodologies to find those intrusions.

We present a parallel implementation of a constraint-based local search algorithm and investigate its performance re- sults on hardware with several hundreds of processors.

GNU Prolog is a general-purpose implementation of the Prolog language, which distinguishes itself from most other systems by being, above all else, a native-code compiler which produces standalone executables which don't rely on any byte-code emulator or meta-interpreter. Other aspects which stand out include the explicit organization of the Prolog system as a multipass compiler, where intermediate representations are materialized, in Unix compiler tradition. GNU Prolog also includes an extensible and high-performance finite domain constraint solver, integrated with the Prolog language but implemented using independent lower-level mechanisms. This article discusses the main issues involved in designing and implementing GNU Prolog: requirements, system organization, performance and portability issues as well as its position with respect to other Prolog system implementations and the ISO standardization initiative., 30 pages, 3 figures, To appear in Theory and Practice of Logic Programming (TPLP); Keywords: Prolog, logic programming system, GNU, ISO, WAM, native code compilation, Finite Domain constraints

International audience; We investigate the use of the Cell Broadband Engine (Cell/BE) for Combinatorial Optimization applications. We present a parallel version of a constraint-based Local Search algorithm which was chosen because it fits very well the Cell/BE architecture since it requires neither shared memory nor communication between processors. The performance study on several large optimization benchmarks shows mostly linear time speedups, even sometimes super-linear. These experiments were done on a Dual-Cell IBM Blade with 16 processors. Besides getting speedups, the execution times exhibit a much smaller variance, which benefits applications where a timely reply is critical.

International audience; We explore the use of the Cell Broadband Engine (Cell/BE for short) for combinatorial optimization applications: we present a parallel version of a constraint-based local search algorithm that has been implemented on a multiprocessor BladeCenter machine with twin Cell/BE processors (total of 16 SPUs per blade). This algorithm was chosen because it fits very well the Cell/BE architecture and requires neither shared memory nor communication between processors, while retaining a compact memory footprint. We study the performance on several large optimization benchmarks and show that this achieves mostly linear time speedups, even sometimes super-linear. This is possible because the parallel implementation might explore simultaneously different parts of the search space and therefore converge faster towards the best sub-space and thus towards a solution. Besides getting speedups, the resulting times exhibit a much smaller variance, which benefits applications where a timely reply is critical.

International audience; The current proposals for the inclusion of modules in the ISO Prolog standard are not very consensual. Since a program-structuring feature is required for a production programming language, several alternatives have been explored over the years. In this article we recall and expand on the concepts of Contextual Logic Programming, a powerful and simple mechanism which addresses the general issue of modularity in Logic Programs. We claim that unit arguments are an essential addition to this programming model, illustrate the claim with examples and draw parallels with Object-Oriented programming. We argue that Contextual Logic Programming is an interesting and effective tool for the development of large-scale programs built upon the Contextual Logic Programming paradigm and argue that contexts with arguments actually provide a powerful, expressive and very convenient means of structuring large applications upon a Prolog basis. We substantiate our claims with examples taken mostly from a "real world" application, Universidade de Evora's ' Academic Information System, which is currently being developed using the prototype implementation described in this article. We sketch the most relevant aspects of a new implementation of Contextual Logic Programming, GNU Prolog/CX, focusing on the impact on performance of the features which were added to a regular Prolog system, highlighting the low overhead which is incurred in case these extensions are not used

International audience; In this study, we started to investigate how the Partitioned Global Address Space (PGAS) programming language X10 would suit the implementation of a Constraint-Based Local Search solver. We wanted to code in this language because we expect to gain from its ease of use and independence from specifi c parallel architectures. We present the implementation strategy, and search for di fferent sources of parallelism. We discuss the algorithms, their implementations and present a performance evaluation on a representative set of benchmarks.