Pasar al contenido principal

MODELOS Y METODOS BASADOS EN GRAFOS PARA LA COMPUTACION EN GRAN ESCALA

TIN2017-86727-C2-1-R

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2017
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 63
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

State-based encoding of large asynchronous controllers

  • Moreno, Albert
  • Cortadella, Jordi|||0000-0001-8114-250X
State encoding is one of the fundamental problems in the synthesis of asynchronous controllers. The requirement for a correct hazard-free implementation imposes severe constraints on the way encoding signals can be inserted in the specification of a controller. Even though some specification formalisms, such as Burst-mode machines or Signal Transition Graphs, enable to specify behaviors at the event level, the state encoding methods that provide the best good-quality solutions work at the state level. This imposes a severe limitation on the size of the controllers that can be handled by these methods. This paper proposes a method to solve the encoding problem for large asynchronous controllers using statebased methods. It is based on an iterative process of projection and re-composition that reduces the size specification by hiding signals, partially solves the encoding problem at the state level and re-composes the original specification using a synchronous product. The process iterates until all encoding conflicts have been solved. The method is proved to preserve the behavior of the specification (branching bisimilarity) and shown to be capable of providing good-quality solutions for controllers of more than 100 signals and 106 states., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Algorithmically efficient syntactic characterization of possibility domains

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Kirousis, Lefteris
  • Kokonezi, Sofia
  • Livieratos, John
In the field of Judgment Aggregation, a domain, that is a subset of a Cartesian power of {0, 1}, is considered to reflect abstract rationality restrictions on vectors of two-valued judgments on a number of issues. We are interested in the ways we can aggregate the positions of a set of individuals, whose positions over each issue form vectors of the domain, by means of unanimous (idempotent) functions, whose output is again an element of the domain. Such functions are called non-dictatorial, when their output is not simply the positions of a single individual. Here, we consider domains admitting various kinds of non-dictatorial aggregators, which reflect various properties of majority aggregation: (locally) non-dictatorial, generalized dictatorships, anonymous, monotone, StrongDem and systematic. We show that interesting and, in some sense, democratic voting schemes are always provided by domains that can be described by propositional formulas of specific syntactic types we define. Furthermore, we show that we can efficiently recognize such formulas and that, given a domain, we can both efficiently check if it is described by such a formula and, in case it is, construct it. Our results fall in the realm of classical results concerning the syntactic characterization of domains with specific closure properties, like domains closed under logical AND which are the models of Horn formulas. The techniques we use to obtain our results draw from judgment aggregation as well as propositional logic and universal algebra., The first two authors’ research was partially supported by TIN2017-86727-C2-1-R, GRAMM. The research of the second author was carried out while visiting the Computer Science Department of the Universitat Politècnica de Catalunya., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Buffer placement and sizing for high-performance dataflow circuits

  • Josipovic, Lana
  • Sheikhha, Shabnam
  • Guerrieri, Andrea
  • Ienne, Paolo
  • Cortadella, Jordi|||0000-0001-8114-250X
Commercial high-level synthesis tools typically produce statically scheduled circuits. Yet, effective C-to-circuit conversion of arbitrary software applications calls for dataflow circuits, as they can handle efficiently variable latencies (e.g., caches), unpredictable memory dependencies, and irregular control flow. Dataflow circuits exhibit an unconventional property: registers (usually referred to as “buffers”) can be placed anywhere in the circuit without changing its semantics, in strong contrast to what happens in traditional datapaths. Yet, although functionally irrelevant, this placement has a significant impact on the circuit’s timing and throughput. In this work, we show how to strategically place buffers into a dataflow circuit to optimize its performance. Our approach extracts a set of choice-free critical loops from arbitrary dataflow circuits and relies on the theory of marked graphs to optimize the buffer placement and sizing. Our performance optimization model supports important high-level synthesis features such as pipelined computational units, units with variable latency and throughput, and if-conversion. We demonstrate the performance benefits of our approach on a set of dataflow circuits obtained from imperative code., L. Josipović was supported by a Google Ph.D. Fellowship in Systems and Networking. J. Cortadella was supported by grants MINECO TIN2017-86727-C2-1-R and GENCAT 2017-SGR-786, Peer Reviewed, Award-winning
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Computing alignments of well-formed process models using local search

  • Taymouri, Farbod
  • Carmona Vargas, Josep|||0000-0001-9656-254X
The alignment of observed and modeled behavior is an essential element for organizations, since it opens the door for conformance checking and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. In this article, a novel approach is presented to tackle the challenge of computing an alignment for large-problem instances that correspond to well-formed process models. Given an observed trace, first it uses a novel replay technique to find an initial candidate trace in the model. Then a local search framework is applied to try to improve the alignment until no further improvement is possible. The implementation of the presented technique reveals a magnificent reduction both in computation time and in memory usage. Moreover, although the proposed technique does not guarantee the derivation of an alignment with minimal cost, the experiments show that in practice the quality of the obtained solutions is close to optimal., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Some results of Maria Serna on strategic games: Complexity of equilibria and models

  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Duch Brown, Amalia|||0000-0003-4371-1286
We survey some recent work of Maria Serna concerning strategic games. We first examine some results related to the formal representation of strategic games and the complexity of problems related to both the existence of equilibria and the equivalence of games. These results provided a better understanding of how the succinctness of the game representation affects the complexity of such problems. We then describe some work dealing with the definition of new strategic games. The study of a Network Formation Game with asymmetric players, and the introduction of Celebrity Games as well as of Strategic Search Games intend to explain the natural behaviour of agents acting in some particular environments like communication networks, social networks, or even networks that contain valuable items hidden in different nodes., This work was partially supported by funds from the AGAUR, Spain of the Government of Catalonia under project ref. 2017 SGR 786 (ALBCOM), by the Spanish Ministry for Economy and Competitiveness (MINECO), Spain and by the European Union (FEDER funds), under grants ref. TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Conformance checking in UML artifact-centric business process models

  • Estañol Lamarca, Montserrat|||0000-0001-7204-932X
  • Muñoz Gama, Jorge|||0000-0002-6908-3911
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Teniente López, Ernest|||0000-0001-8890-9638
Business artifacts have appeared as a new paradigm to capture the information required for the complete execution and reasoning of a business process. Likewise, conformance checking is gaining popularity as a crucial technique that enables evaluating whether recorded executions of a process match its corresponding model. In this paper, conformance checking techniques are incorporated into a general framework to specify business artifacts. By relying on the expressive power of an artifact-centric specification, BAUML, which combines UML state and activity diagrams (among others), the problem of conformance checking can be mapped into the Petri net formalism and its results be explained in terms of the original artifact-centric specification. In contrast to most existing approaches, ours incorporates data constraints into the Petri nets, thus achieving conformance results which are more precise. We have also implemented a plug-in, within the ProM framework, which is able to translate a BAUML into a Petri net to perform conformance checking. This shows the feasibility of our approach., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Satisfaction and power in unanimous majority influence decision models

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
We consider decision models associated with cooperative influence games, the oblivious and the non-oblivious influence models. In those models the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures when the in uence level is set to unanimity and the rule of decision is simple majority. We show that computing the satisfaction and the power measure in those systems are #P-hard., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Robustness to voltage noise with ring oscillator clocks

  • Machado, Lucas
  • Roca Pérez, Antoni|||0000-0002-1083-4565
  • Cortadella, Jordi|||0000-0001-8114-250X
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Voltage noise is the main source of dynamic variability in integrated circuits and a major concern for the design of power delivery networks (PDNs). Lower supply voltages were made possible with technology scaling, but power density was also increased. Consequently, power integrity became a key factor in the design of reliable high performance circuits. Ring oscillators clocks (ROCs) have been proposed as an alternative to mitigate the negative effects of voltage noise. However, the effectiveness highly depends on the design parameters of the PDN, power consumption patterns, and spatial locality of the ROC within the clock domain. This paper analyzes the impact of the PDN parameters and ROC location on the voltage noise and the robustness achieved by using ROCs. The capability of reacting instantaneously to large voltage droops makes ROCs an attractive solution, which also allows to relax the constraints required for the PDN design. The experiments show that up to 83% of the margins for voltage noise and up to 27% of the total leakage power can be reduced by using ROCs. In addition, PDN simplifications are possible, with fewer power interconnections or package decoupling capacitors of lower quality. Tolerance to voltage noise and related benefits can be increased with multiple ROCs., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Anti-alignments—Measuring the precision of process models and event logs

  • Chatain, Thomas
  • Boltenhagen, Mathilde
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Processes are a crucial artifact in organizations, since they coordinate the execution of activities so that products and services are provided. The use of models to analyze the underlying processes is a well-known practice. However, due to the complexity and continuous evolution of their processes, organizations need an effective way of analyzing the relation between processes and models. Conformance checking techniques assess the suitability of a process model in representing an underlying process, observed through a collection of real executions. One important metric in conformance checking is to assess the precision of the model with respect to the observed executions, i.e., characterize the ability of the model to produce behavior unrelated to the one observed. In this paper we present the notion of anti-alignment as a concept to help unveiling runs in the model that may deviate significantly from the observed behavior. Using anti-alignments, a new metric for precision is proposed. The proposed anti-alignment based precision metric satisfies most of the required axioms highlighted in a recent publication. Moreover, a complexity analysis of the problem of computing anti-alignments is provided, which sheds light into the practicability of using anti-alignment to estimate precision. Experiments are provided that witness the validity of the concepts introduced in this paper., This work has been partially supported by funds from ENS Paris-Saclay, Spain (project ProMAut of the Farman institute), the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Empowering conformance checking using Big Data through horizontal decomposition

  • Valencia Parra, Álvaro
  • Varela Vaca, Ángel Jesús
  • Gómez López, María Teresa
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Bergenthum, Robin
Conformance checking unleashes the full power of process mining: techniques from this discipline enable the analysis of the quality of a process model through the discovery of event data, the identification of potential deviations, and the projection of real traces onto process models. In this way, the insights gained from the available event data can be transferred to a richer conceptual level, amenable for human interpretation. Unfortunately, most of the aforementioned functionalities are grounded in an extremely difficult fundamental problem: given an observed trace and a process model, find the model trace that most closely resembles to the trace observed. This paper presents an architecture that supports the creation and distribution of alignment subproblems based on an innovative horizontal acyclic model decomposition, disengaged from the conformance checking algorithm applied for their solution. This is supported by a Big Data infrastructure that facilitates the customised distribution of a gross amount of data. Experiments are provided that testify to the enormous potential of the architecture proposed, thereby opening the door to further research in several directions., This work has been partially funded by the Ministry of Science and Technology of Spain ECLIPSE (RTI2018-094283-B-C33) project, the European Regional Development Fund (ERDF/FEDER), MINECO (TIN2017-86727-C2-1-R), and by the University of Seville with VI Plan Propio de Investigación y Transferencia (VI PPIT-US)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Unleashing textual descriptions of business processes

  • Sànchez-Ferreres, Josep|||0000-0002-7204-4307
  • Burattin, Andrea
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Montali, Marco
  • Padró, Lluís|||0000-0003-4738-5019
  • Quishpi Betún, Luis Hernán|||0000-0002-3539-5853
Textual descriptions of processes are ubiquitous in organizations, so that documentation of the important processes can be accessible to anyone involved. Unfortunately, the value of this rich data source is hampered by the challenge of analyzing unstructured information. In this paper we propose a framework to overcome the current limitations on dealing with textual descriptions of processes. This framework considers extraction and analysis and connects to process mining via simulation. The framework is grounded in the notion of annotated textual descriptions of processes, which represents a middle-ground between formalization and accessibility, and which accounts for different modeling styles, ranging from purely imperative to purely declarative. The contributions of this paper are implemented in several tools, and case studies are highlighted., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Model-based trace variant analysis of event logs

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep|||0000-0001-9656-254X
The comparison of trace variants of business processes opens the door for a fine-grained analysis of the distinctive features inherent in the executions of a process in an organization. The current approaches for trace variant analysis do not consider the situation where a process model is present, and therefore, it can guide the derivation of the trace variants by considering high-level structures present in the process model. In this paper we propose a fresh alternative to trace variant analysis, which proposes a generalized notion of trace variant that incorporates concurrency and iteration. This way, the analyst may be relieved from analyzing trace variants that are essentially the same, if these aspects are disregarded. We propose a general algorithm for model based trace variant analysis which is grounded in encoding the problem into SAT, and a family of heuristic alternatives including a very light sampling technique that represents a good trade-off between quality of the trace variants identified, and the complexity of the analysis. All the techniques of the paper are implemented in two open-source tools, and experiments with publicly available benchmarks are reported., This work has been supported by Farman institute at ENS Paris-Saclay, Spain and by MINECO, Spain and FEDER, Spain funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Power-optimal mapping of CNN applications to cloud-based Multi-FPGA platforms

  • Shan, Junnan
  • Lazarescu, Mihai T.
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Lavagno, Luciano
  • Casu, Mario R.
Multi-FPGA platforms like Amazon Web Services F1 are perfect to accelerate multi-kernel pipelined applications, like Convolutional Neural Networks (CNNs). To reduce energy consumption, we propose to upload at runtime the best power-optimized CNN implementation for a given throughput constraint. Our design method gives the best number of parallel instances of each kernel, their allocation to the FPGAs, the number of powered-on FPGAs and their clock frequency. This is obtained by solving a mixed-integer, non-linear optimization problem that models power and performance of each component, as well as the duration of the computation phases-data transfer between a host CPU and the FPGA memory (typically DDR), data transfer between DDR and FPGA, and FPGA computation. The results show that the power saved compared to simply clock gating the fastest implementation is obviously very high, but it is also much more significant than simply scaling the frequency of the fastest implementation or replicating the slowest implementation on multiple FPGAs., This work was partially supported in part by the European Commission through the ECOSCALE Project under Grant H2020-ICT671632, in part by the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER Funds) under Grant TIN2017-86727-C2-1- R and Grant FPI 2015, and in part by the Generalitat de Catalunya under Grant 2017 SGR 786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Automated repair of process models with non-local constraints using state-based region theory

  • Kalenkova, Anna
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Polyvyanyy, Artem
  • La Rosa, Marcello
State-of-the-art process discovery methods construct free-choice process models from event logs. Consequently, the constructed models do not take into account indirect dependencies between events. Whenever the input behaviour is not free-choice, these methods fail to provide a precise model. In this paper, we propose a novel approach for enhancing free-choice process models by adding non-free-choice constructs discovered a-posteriori via region-based techniques. This allows us to benefit from the performance of existing process discovery methods and the accuracy of the employed fundamental synthesis techniques. We prove that the proposed approach preserves fitness with respect to the event log while improving the precision when indirect dependencies exist. The approach has been implemented and tested on both synthetic and real-life datasets. The results show its effectiveness in repairing models discovered from event logs., This work was partly supported by the Australian Research Council Discovery Project DP180102839. This work was supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A tour in process mining: from practice to algorithmic challenges

  • Van der Aalst, Wil M.P.
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Chatain, Thomas
  • Dongen, Boudewijn F. van
Process mining seeks the confrontation between modeled behavior and observed behavior. In recent years, process mining techniques managed to bridge the gap between traditional model-based process analysis (e.g., simulation and other business process management techniques) and data-centric analysis techniques such as machine learning and data mining. Process mining is used by many data-driven organizations as a means to improve performance or to ensure compliance. Traditionally, the focus was on the discovery of process models from event logs describing real process executions. However, process mining is not limited to process discovery and also includes conformance checking. Process models (discovered or hand-made) may deviate from reality. Therefore, we need powerful means to analyze discrepancies between models and logs. These are provided by conformance checking techniques that first align modeled and observed behavior, and then compare both. The resulting alignments are also used to enrich process models with performance related information extracted from the event log. This tutorial paper focuses on the control-flow perspective and describes a range of process discovery and conformance checking techniques. The goal of the paper is to show the algorithmic challenges in process mining. We will show that process mining provides a wealth of opportunities for people doing research on Petri nets and related models of concurrency., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

CNN-on-AWS: Efficient allocation of multikernel applications on Multi-FPGA platforms

  • Shan, Junnan
  • Lazarescu, Mihai T.
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Lavagno, Luciano
  • Casu, Mario R.
Multi-FPGA platforms, like Amazon AWS F1, can run in the cloud multikernel pipelined applications, like convolutional neural networks (CNNs), with excellent performance and lower energy consumption than CPUs or GPUs. We propose a method to efficiently map these applications on multi-FPGA platforms to maximize the application throughput. Our methodology finds, for the given resources, the optimal number of parallel instances of each kernel in the pipeline and their allocation to one or more among the available FPGAs. We obtain this by formulating and solving a mixed-integer, nonlinear optimization problem, in which we model the performance of each component and the duration of the phases in which the accelerated computation can be split into, namely: 1) data transfer from a host CPU to the DDR memory of each FPGA; 2) data transfer from FPGA DDR to FPGA on-chip memory; 3) kernel computation on the FPGA; 4) data transfer from FPGA on-chip memory to FPGA DDR; and 5) data transfer from FPGA DDR to host. Finding the optimal solution using a mixed-integer nonlinear programming (MINLP) solver is often highly inefficient. Hence, we provide a fast heuristic method that according to our experiments can be much more efficient than the MINLP solver and finds comparable results. For larger problems (more CNN layers), our heuristic method can quickly find (several thousand times faster) much better solutions than the MINLP solver, even if we run the latter for a very long time., This work was supported in part by the European Commission through the ECOSCALE Project under Grant H2020-ICT671632, in part by the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER funds) under Grant TIN2017-86727-C2-1-R and Grant FPI 2015, and in part by the Generalitat de Catalunya under Grant 2017 SGR 786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Automatic safe data reuse detection for the WCET analysis of systems with data caches

  • Segarra Flor, Juan
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Gran Tejero, Rubén
  • Viñals Yúfera, Victor
Worst-case execution time (WCET) analysis of systems with data caches is one of the key challenges in real-time systems. Caches exploit the inherent reuse properties of programs, temporarily storing certain memory contents near the processor, in order that further accesses to such contents do not require costly memory transfers. Current worst-case data cache analysis methods focus on specific cache organizations (LRU, locked, ACDC, etc.). In this article, we analyze data reuse (in the worst case) as a property of the program, and thus independent of the data cache. Our analysis method uses Abstract Interpretation on the compiled program to extract, for each static load/store instruction, a linear expression for the address pattern of its data accesses, according to the Loop Nest Data Reuse Theory. Each data access expression is compared to that of prior (dominant) memory instructions to verify whether it presents a guaranteed reuse. Our proposal manages references to scalars, arrays, and non-linear accesses, provides both temporal and spatial reuse information, and does not require the exploration of explicit data access sequences. As a proof of concept we analyze the TACLeBench benchmark suite, showing that most loads/stores present data reuse, and how compiler optimizations affect it. Using a simple hit/miss estimation on our reuse results, the time devoted to data accesses in the worst case is reduced to 27% compared to an always-miss system, equivalent to a data hit ratio of 81%. With compiler optimization, such time is reduced to 6.5%., This work was supported in part by MINECO/AEI/ERDF (EU) under Grant TIN2016-76635-C2-1-R, Grant TIN2017-86727-C2-1-R, and Grant PID2019-105660RB-C21; in part by the Aragón Government under Grant T58_20R research group; in part by the Generalitat de Catalunya under Grant 2017 SGR 786 and Grant FI-DGR 2015; and in part by the Construyendo Europa desde Aragón under Grant ERDF 2014-2020., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Learning random points from geometric graphs or orderings

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Mcdiarmid, Colin
  • Mitsche, Dieter
Let Xv for v∈V be a family of n iid uniform points in the square (Formula presented.). Suppose first that we are given the random geometric graph (Formula presented.), where vertices u and v are adjacent when the Euclidean distance dE(Xu,Xv) is at most r. Let n3/14≪r≪n1/2. Given G (without geometric information), in polynomial time we can with high probability approximately reconstruct the hidden embedding, in the sense that “up to symmetries,” for each vertex v we find a point within distance about r of Xv; that is, we find an embedding with “displacement” at most about r. Now suppose that, instead of G we are given, for each vertex v, the ordering of the other vertices by increasing Euclidean distance from v. Then, with high probability, in polynomial time we can find an embedding with displacement (Formula presented.)., This research was supported by the grants GRAMM, TIN2017-86727-C2-1-R (J.D.), and by IDEXLYON of Université de Lyon (Programme Investissements d’Avenir, ANR16-IDEX-0005), and by LABEXMILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) (D.M.), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Knowledge-based segmentation to improve accuracy and explainability in non-technical losses detection

  • Calvo Ibáñez, Albert|||0000-0002-3761-9478
  • Coma Puig, Bernat|||0000-0003-3944-797X
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Arias Vicente, Marta|||0000-0001-7359-1815
Utility companies have a great interest in identifying energy losses. Here, we focus on Non-Technical Losses (NTL), which refer to losses caused by utility theft or meter errors. Typically, utility companies resort to machine learning solutions to automate and optimise the identification of such losses. This paper extends an existing NTL-detection framework: by including knowledge-based NTL segmentation, we have detected some opportunities for improving the accuracy and the explanations provided to the utility company. Our improved models focus on specific types of NTL and therefore, the explanations provided are easier to interpret, allowing stakeholders to make more informed decisions. The improvements and results presented in the article may benefit other industrial frameworks., This work has been supported by MINECO and FEDER funds under grants TIN2017-86727-C2-1-R and TIN2017-89244-R, the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya)., Peer Reviewed, Objectius de Desenvolupament Sostenible::9 - Indústria, Innovació i Infraestructura
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Maria Serna’s contributions to adversarial queuing theory

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Fernández Anta, Antonio
Adversarial Queuing Theory (aqt) is one of the areas to which Maria Serna has deeply contributed in her scientific career. Most of her research in this area took place during the lustrum 2001–2005, while advising the Ph.D. of Maria J. Blesa (2006) [1], and also in conjunction with other researchers. aqt is an adversarial model for the study of packet-switching communication networks under worst case conditions. In this model a fundamental concept is that of stability of a combination of network and packet scheduling protocol in front of an adversary that controls the arrival of packets. There is stability if the adversary cannot cause the number of packets in the network to grow unbounded. Maria’s contributions, summarized in this document, include results in the stability of networks and protocols, and the definition and study of aqt models with important new characteristics, like priorities, failures, or networks with different bandwidths and packet lengths. These results keep impacting the new research currently done in the aqt model., This research has been partially supported by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under project 2017 SGR 786 (ALBCOM) and by MINECO and FEDER funds under grant GRAMM (ref. TIN2017-86727-C2-1-R)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Computation of alignments of business processes through relaxation labelling and local optimal search

  • Padró, Lluís|||0000-0003-4738-5019
  • Carmona Vargas, Josep|||0000-0001-9656-254X
A fundamental problem in conformance checking is aligning event data with process models. Unfortunately, existing techniques for this task are either complex, or can only be applicable to restricted classes of models. This in practice means that for large inputs, current techniques often fail to produce a result. In this paper we propose a method to compute alignments for unconstrained process models, which relies on the use of relaxation labelling techniques on top of a partial order representation of the process model. The technique proposed in this paper precomputes information used in the search for alignments, and is able to produce real alignments that may be close to optimal ones by combining the aforementioned techniques with a locally applied A strategy. Remarkably, the implementation on the proposed technique achieves a speed-up of several orders of magnitude with respect to the approaches in the literature (either optimal, sup-optimal or approximate), often with a reasonable trade-off on the cost of the obtained alignment., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Multi-level dataflow-driven macro placement guided by RTL structure and analytical methods

  • Vidal Obiols, Alexandre|||0000-0002-7016-0160
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Petit Silvestre, Jordi|||0000-0001-8331-8126
  • Galcerán Oms, Marc
  • Martorell Cid, Ferran
When RTL designers define the hierarchy of a system, they exploit their knowledge about the conceptual abstractions devised during the design and the functional interactions between the logical components. This valuable information is often lost during physical synthesis. This paper proposes HiDaP, a novel multi-level algorithm that uses RTL information and analytical methods for the macro placement problem of modern designs dominated by multi-cycle connection pipelines. By taking advantage of the hierarchy tree, the netlist is divided into blocks containing macros and standard cells, and their dataflow affinity is inferred considering the register latency and flow width of their interaction. The layout is represented using slicing structures and generated with a top-down algorithm capable of handling blocks with both hard and soft components. An adaptive multi-objective cost function is used to simultaneously minimize wirelength, timing, overlap and distance to preferred locations, which can be user-defined or generated by analytic methods (spectral and force-directed). These techniques have been applied to a set of large industrial circuits and compared against state-of-theart commercial and academic placers, and also to handcrafted floorplans generated by expert back-end engineers. The proposed approach outperforms previous algorithmic methods and can produce solutions with better wirelength and timing than the best handcrafted floorplans. Post-routing layouts are almost brought to timing closure and DRC cleanness with minimal engineer modification, showing that the generated floorplans provide an excellent starting point for the physical design flow and contribute to reduce turn-around time significantly., This work has been partially supported by a grant from Inphi Corporation and funds from the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER funds) under grant TIN2017-86727-C2-1-R, and the Generalitat de Catalunya (2017 SGR 786)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the PoA conjecture: Trees versus biconnected components

  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Messegué Buisan, Arnau|||0000-0002-7425-7592
In the classical model of network creation games introduced by Fabrikant et al. [Ona network creation game, in Proceedings of the Twenty-Second Annual Symposium on Principlesof Distributed Computing (PODC`03), 2003, pp. 347--351],nplayers correspond to the nodes of anetwork buying links of price\alpha and to the other players with the goal of being well-connected tothe resulting network. Still as an open problem, theconstantPoAconjecturestates that thePriceof Anarchy(PoA) is constant for any\alpha . When tackling this problem distinct behaviors must betaken into the account depending on whether\alpha has either large or low value. It is known that for\alpha >4n - 13 everyneis a tree and for\alpha =O(n1 - \delta ) with\delta \geq 1/lognthe diameter of networks thatare in equilibrium when restricting to deviations that consist only in buying links (buying equilibria)is at most a constant. These results imply that the PoA is constant for the disjoint union of thetwo ranges, and thus the constant PoA conjecture seems to be true for most of all the possiblevalues\alpha . In this paper we study the PoA for the remaining range of\alpha and we show the following:(i) For\alpha > n(1 +\epsilon ) the PoA is constant by proving that the size of any biconnected componentof an equilibrium graph is constant. (ii) For\alpha \leq n(1 +\epsilon ) we have that PoA = \Theta (dmax), wheredmaxis the maximum diameter of an equilibrium graph for the same range of\alpha . Therefore if theconstant PoA conjecture was false, it would suffice to construct equilibria of nonconstant diameter.Towards this direction we find nontrivialbuying equilibriaof nonconstant diameter when\alpha > n1 - \delta and\delta =O(2 - \surd \mathrm{l}\mathrm{o}\mathrm{g}n), exploring new intimate relationships betweendistance-uniform graphsandbuying equilibria., This work was partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R), from the European Union-NextGenerationEU under Margarita Salas, from UPC grant 2021UPC-MS-66935, and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Refining indeterministic choice: Imprecise probabilities and strategic thinking

  • Castro Rabal, Jorge|||0000-0002-1390-1313
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Serna Iglesias, María José|||0000-0001-9729-8648
Often, uncertainty is present in processes that are part of our routines. Having tools to understand the consequences of unpredictability is convenient. We introduce a general framework to deal with uncertainty in the realm of distribution sets that are descriptions of imprecise probabilities. We propose several non-biased refinement strategies to obtain sensible forecasts about results of uncertain processes. Initially, uncertainty on a system is modeled as the non-deterministic choice of its possible behaviors. Our refinement hypothesis translates non-determinism into imprecise probabilistic choices. Imprecise probabilities allow us to propose a notion of uncertainty refinement in terms of set inclusions. Later on, unpredictability is tackled through a strategic approach using uncertainty profiles and angel/daemon games ([Formula: see text]-games). Here, imprecise probabilities form the set of mixed strategies and Nash equilibria corresponds to natural uncertainty refinements. We use this approach to study the performance of Web applications — in terms of response times — under stress conditions., J. Castro was partially supported by MINECO and EU FEDER funds grant TIN2017-89244-R and AGAUR grant 2017 SGR-856.J. Gabarro and M. Serna were partially supported by MINECO and EU FEDER funds grant TIN2017-86727-C2-1-R and AGAUR 2017 SGR 786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A navigational logic for reasoning about graph properties

  • Navarro Gómez, Marisa
  • Orejas Valdés, Fernando|||0000-0002-3023-4006
  • Pino Blanco, Elvira|||0000-0003-3376-5096
  • Lambers, Leen
Graphs play an important role in many areas of Computer Science. In particular, our work is motivated by model-driven software development and by graph databases. For this reason, it is very important to have the means to express and to reason about the properties that a given graph may satisfy. With this aim, in this paper we present a visual logic that allows us to describe graph properties, including navigational properties, i.e., properties about the paths in a graph. The logic is equipped with a deductive tableau method that we have proved to be sound and complete., This work was supported by the Spanish Ministry of Economy and Competitiveness and the European Union (FEDER funds) under grant GRAMM (ref. TIN2017-86727-C2-1-R, TIN2017-86727-C2-2-R) and by the Basque Project GIU15/30, and grant UFI11/45., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Dynamic pipelining of multidimensional range queries

  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Lugosi, Daniel
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Zoltan Torres, Ana Cristina
The problem of evaluating orthogonal range queries efficiently has been studied widely in the data structures community. It has been common wisdom for several years that for queries containing more than 20% of the elements of the dataset a linear scanning of the data was the most efficient solution. In recent experimental works using modern hardware –with main memory and parallelism– the conclusion is that linear scan is preferable for almost every query configuration (even containing a 1% of the data). In this work we propose an alternative approach to evaluate multidimensional range queries based on the dynamic pipeline paradigm –using main memory and concurrency. Our aim is to prove that under this framework, it is possible to beat the performance of linear scanning by the one of hierarchical multidimensional data structures –such as kd trees, quad trees, Rtrees or similar., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Bridging the gap between energy consumption and distribution through non-technical loss detection

  • Coma Puig, Bernat|||0000-0003-3944-797X
  • Carmona Vargas, Josep|||0000-0001-9656-254X
The application of Artificial Intelligence techniques in industry equips companies with new essential tools to improve their principal processes. This is especially true for energy companies, as they have the opportunity, thanks to the modernization of their installations, to exploit a large amount of data with smart algorithms. In this work we explore the possibilities that exist in the implementation of Machine-Learning techniques for the detection of Non-Technical Losses in customers. The analysis is based on the work done in collaboration with an international energy distribution company. We report on how the success in detecting Non-Technical Losses can help the company to better control the energy provided to their customers, avoiding a misuse and hence improving the sustainability of the service that the company provides., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Flexible process model mapping using relaxation labeling

  • Delicado Alcántara, Luis
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Padró, Lluís|||0000-0003-4738-5019
Computing a mapping between two process models is a crucial technique, since it enables reasoning and operating across processes, like providing a similarity score between two processes, or merging different process variants to generate a consolidated process model. In this paper we present a new flexible technique for process model mapping, based on the relaxation labeling constraint satisfaction algorithm. The technique can be instantiated so that different modes are devised, depending on the context. For instance, it can be adapted to the case where one of the mapped process models is incomplete, or it can be used to ground an adaptable similarity measure between process models. The approach has been implemented inside the open platform NLP4BPM, providing a visualization of the performed mappings and computed similarity scores. The experimental results witness the flexibility and usefulness of the technique proposed., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Optimized SAT encoding of conformance checking artefacts

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Conformance checking is a growing discipline that aims at assisting organizations in monitoring their processes. On its core, conformance checking relies on the computation of particular artefacts which enable reasoning on the relation between observed and modeled behavior. It is widely acknowledge that the computation of these artifacts is the lion’s share of conformance checking techniques. This paper shows how important conformance artefacts like alignments, anti-alignments or multi-alignments, defined over the Levenshtein edit distance, can be efficiently computed by encoding the problem as an optimized SAT instance. From a general perspective, the work advocates for a unified family of techniques that can compute conformance artefacts in the same way. The implementation of the techniques presented in this paper show capabilities for dealing with both synthetic and real-life instances, which may open the door for a fresh way of applying conformance checking in the near future., This work has been supported by Farman institute at ENS Paris-Saclay and by MINECO and FEDER funds under Grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Support-reducing decomposition for FPGA mapping

  • Machado, Lucas
  • Cortadella, Jordi|||0000-0001-8114-250X
Decomposition is a technology-independent process, in which a large complex function is broken into smaller, less complex functions. The costs of two-level or factored-form representations (cubes and literals) are used in most decomposition methods, as they have a high correlation with the area of cell-based designs. However, this correlation is weaker for field-programmable gate arrays (FPGAs) based on look-up tables. Furthermore, local optimizations have limited power due to the structural bias of the circuit descriptions. This paper tries to reduce the structural biasing by remapping the LUT network and decomposing the derived functions using the support as cost function. The proposed method improves the FPGA mapping results of a commercial tool for the 20 largest MCNC benchmarks, with gains of 28% in delay plus 18% in area when targeting delay, and a reduction of 28% in area plus 14% in delay with area as cost function. Results with 23% less area and 6% less delay are obtained after physical synthesis (post place-and-route). Moreover, 12 of the best known results for delay (and 3 for area) of the EPFL benchmarks are improved., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Supporting the process of learning and teaching process models

  • Sànchez-Ferreres, Josep|||0000-0002-7204-4307
  • Delicado Alcántara, Luis
  • Andaloussi, Amine Abbad
  • Burattin, Andrea
  • Calderón Ruiz, Guillermo
  • Weber, Barbara
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Padró, Lluís|||0000-0003-4738-5019
The creation of a process model faces the challenge of constructing a syntactically correct entity which accurately reflects the semantics of the reality, and is understandable. This paper proposes a framework called ModelJudge , focused towards the two main actors in the process of learning process model creation: novice modellers and instructors. For modellers, the platform enables the automatic validation of the process models created from the textual description, providing explanations about quality issues in the model. ModelJudge can provide diagnostics regarding model structure, writing style, and seman- tics by aligning annotated textual descriptions to models. For instructors, the platform facilitates the creation of modelling exercises by providing an editor to annotate the main parts of a textual description, that is empowered with Natural Language Processing (NLP) capabilities so that the annotation effort is minimized. So far around 300 students, in process modelling courses of five different universities around the world have used the platform. The feedback gathered from some of these courses shows good potential in helping students to improve their learning experience, which might, in turn, impact process model quality and understandability. Moreover, our results show that instructors can benefit from getting insights into the evolution of modeling processes including arising quality issues of single students, but also discover tendencies in groups of students. Although the framework has been applied to process model creation, it could be extrapolated to other contexts where the creation of models based on a textual description plays an important role., This work has been partially supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Automatic Safe Data Reuse Detection for the WCET Analysis of Systems With Data Caches

  • Segarra, J.
  • Cortadella, J.
  • Gran Tejero, R.
  • Viñals-Yufera, V.
Worst-case execution time (WCET) analysis of systems with data caches is one of the key challenges in real-time systems. Caches exploit the inherent reuse properties of programs, temporarily storing certain memory contents near the processor, in order that further accesses to such contents do not require costly memory transfers. Current worst-case data cache analysis methods focus on specific cache organizations (LRU, locked, ACDC, etc.). In this article, we analyze data reuse (in the worst case) as a property of the program, and thus independent of the data cache. Our analysis method uses Abstract Interpretation on the compiled program to extract, for each static load/store instruction, a linear expression for the address pattern of its data accesses, according to the Loop Nest Data Reuse Theory. Each data access expression is compared to that of prior (dominant) memory instructions to verify whether it presents a guaranteed reuse. Our proposal manages references to scalars, arrays, and non-linear accesses, provides both temporal and spatial reuse information, and does not require the exploration of explicit data access sequences. As a proof of concept we analyze the TACLeBench benchmark suite, showing that most loads/stores present data reuse, and how compiler optimizations affect it. Using a simple hit/miss estimation on our reuse results, the time devoted to data accesses in the worst case is reduced to 27% compared to an always-miss system, equivalent to a data hit ratio of 81%. With compiler optimization, such time is reduced to 6.5%.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Refining indeterministic choice: Imprecise probabilities and strategic thinking

  • Castro Rabal, Jorge
  • Gabarró Vallès, Joaquim
  • Serna Iglesias, María José
Often, uncertainty is present in processes that are part of our routines. Having tools to understand the consequences of unpredictability is convenient. We introduce a general framework to deal with uncertainty in the realm of distribution sets that are descriptions of imprecise probabilities. We propose several non-biased refinement strategies to obtain sensible forecasts about results of uncertain processes. Initially, uncertainty on a system is modeled as the non-deterministic choice of its possible behaviors. Our refinement hypothesis translates non-determinism into imprecise probabilistic choices. Imprecise probabilities allow us to propose a notion of uncertainty refinement in terms of set inclusions. Later on, unpredictability is tackled through a strategic approach using uncertainty profiles and angel/daemon games ([Formula: see text]-games). Here, imprecise probabilities form the set of mixed strategies and Nash equilibria corresponds to natural uncertainty refinements. We use this approach to study the performance of Web applications — in terms of response times — under stress conditions., J. Castro was partially supported by MINECO and EU FEDER funds grant TIN2017-89244-R and AGAUR grant 2017 SGR-856.J. Gabarro and M. Serna were partially supported by MINECO and EU FEDER funds grant TIN2017-86727-C2-1-R and AGAUR 2017 SGR 786., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Support-reducing decomposition for FPGA mapping

  • Machado, Lucas
  • Cortadella, Jordi
Decomposition is a technology-independent process, in which a large complex function is broken into smaller, less complex functions. The costs of two-level or factored-form representations (cubes and literals) are used in most decomposition methods, as they have a high correlation with the area of cell-based designs. However, this correlation is weaker for field-programmable gate arrays (FPGAs) based on look-up tables. Furthermore, local optimizations have limited power due to the structural bias of the circuit descriptions. This paper tries to reduce the structural biasing by remapping the LUT network and decomposing the derived functions using the support as cost function. The proposed method improves the FPGA mapping results of a commercial tool for the 20 largest MCNC benchmarks, with gains of 28% in delay plus 18% in area when targeting delay, and a reduction of 28% in area plus 14% in delay with area as cost function. Results with 23% less area and 6% less delay are obtained after physical synthesis (post place-and-route). Moreover, 12 of the best known results for delay (and 3 for area) of the EPFL benchmarks are improved., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Knowledge-based segmentation to improve accuracy and explainability in non-technical losses detection

  • Calvo Ibáñez, Albert
  • Coma Puig, Bernat
  • Carmona Vargas, Josep
  • Arias Vicente, Marta
Utility companies have a great interest in identifying energy losses. Here, we focus on Non-Technical Losses (NTL), which refer to losses caused by utility theft or meter errors. Typically, utility companies resort to machine learning solutions to automate and optimise the identification of such losses. This paper extends an existing NTL-detection framework: by including knowledge-based NTL segmentation, we have detected some opportunities for improving the accuracy and the explanations provided to the utility company. Our improved models focus on specific types of NTL and therefore, the explanations provided are easier to interpret, allowing stakeholders to make more informed decisions. The improvements and results presented in the article may benefit other industrial frameworks., This work has been supported by MINECO and FEDER funds under grants TIN2017-86727-C2-1-R and TIN2017-89244-R, the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya)., Peer Reviewed, Objectius de Desenvolupament Sostenible::9 - Indústria, Innovació i Infraestructura, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Evolutionary trajectories of new duplicated and putative de novo genes

  • Montañés Domínguez, José Carlos
  • Huertas Pulido, Marta
  • Messeguer Peypoch, Xavier
  • Albà Soler, Maria del Mar
The formation of new genes during evolution is an important motor of functional innovation, but the rate at which new genes originate and the likelihood that they persist over longer evolutionary periods are still poorly understood questions. Two important mechanisms by which new genes arise are gene duplication and de novo formation from a previously noncoding sequence. Does the mechanism of formation influence the evolutionary trajectories of the genes? Proteins arisen by gene duplication retain the sequence and structural properties of the parental protein, and thus they may be relatively stable. Instead, de novo originated proteins are often species specific and thought to be more evolutionary labile. Despite these differences, here we show that both types of genes share a number of similarities, including low sequence constraints in their initial evolutionary phases, high turnover rates at the species level, and comparable persistence rates in deeper branchers, in both yeast and flies. In addition, we show that putative de novo proteins have an excess of substitutions between charged amino acids compared with the neutral expectation, which is reflected in the rapid loss of their initial highly basic character. The study supports high evolutionary dynamics of different kinds of new genes at the species level, in sharp contrast with the stability observed at later stages., We acknowledge funding from Ministerio de Ciencia e Innovación Agencia Estatal de Investigación grant PGC2018-094091-B-I00 (cofunded by Fondo Europeo de Desarrollo Regional), as well as grants PID2021-122726NB-I00 and PID2021-122830OB-C43 funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”, by the “European Union”. We also acknowledge funding from Generalitat de Catalunya, grant 2021SGR00042. The work was also funded by the European Union (ERC, NovoGenePop, project number 101052538)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Power-optimal mapping of CNN applications to cloud-based Multi-FPGA platforms

  • Shan, Junnan
  • Lazarescu, Mihai T.
  • Cortadella, Jordi
  • Lavagno, Luciano
  • Casu, Mario R.
Multi-FPGA platforms like Amazon Web Services F1 are perfect to accelerate multi-kernel pipelined applications, like Convolutional Neural Networks (CNNs). To reduce energy consumption, we propose to upload at runtime the best power-optimized CNN implementation for a given throughput constraint. Our design method gives the best number of parallel instances of each kernel, their allocation to the FPGAs, the number of powered-on FPGAs and their clock frequency. This is obtained by solving a mixed-integer, non-linear optimization problem that models power and performance of each component, as well as the duration of the computation phases-data transfer between a host CPU and the FPGA memory (typically DDR), data transfer between DDR and FPGA, and FPGA computation. The results show that the power saved compared to simply clock gating the fastest implementation is obviously very high, but it is also much more significant than simply scaling the frequency of the fastest implementation or replicating the slowest implementation on multiple FPGAs., This work was partially supported in part by the European Commission through the ECOSCALE Project under Grant H2020-ICT671632, in part by the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER Funds) under Grant TIN2017-86727-C2-1- R and Grant FPI 2015, and in part by the Generalitat de Catalunya under Grant 2017 SGR 786., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Computing alignments of well-formed process models using local search

  • Taymouri, Farbod
  • Carmona Vargas, Josep
The alignment of observed and modeled behavior is an essential element for organizations, since it opens the door for conformance checking and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. In this article, a novel approach is presented to tackle the challenge of computing an alignment for large-problem instances that correspond to well-formed process models. Given an observed trace, first it uses a novel replay technique to find an initial candidate trace in the model. Then a local search framework is applied to try to improve the alignment until no further improvement is possible. The implementation of the presented technique reveals a magnificent reduction both in computation time and in memory usage. Moreover, although the proposed technique does not guarantee the derivation of an alignment with minimal cost, the experiments show that in practice the quality of the obtained solutions is close to optimal., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Automatic safe data reuse detection for the WCET analysis of systems with data caches

  • Segarra Flor, Juan
  • Cortadella, Jordi
  • Gran Tejero, Rubén
  • Viñals Yúfera, Victor
Worst-case execution time (WCET) analysis of systems with data caches is one of the key challenges in real-time systems. Caches exploit the inherent reuse properties of programs, temporarily storing certain memory contents near the processor, in order that further accesses to such contents do not require costly memory transfers. Current worst-case data cache analysis methods focus on specific cache organizations (LRU, locked, ACDC, etc.). In this article, we analyze data reuse (in the worst case) as a property of the program, and thus independent of the data cache. Our analysis method uses Abstract Interpretation on the compiled program to extract, for each static load/store instruction, a linear expression for the address pattern of its data accesses, according to the Loop Nest Data Reuse Theory. Each data access expression is compared to that of prior (dominant) memory instructions to verify whether it presents a guaranteed reuse. Our proposal manages references to scalars, arrays, and non-linear accesses, provides both temporal and spatial reuse information, and does not require the exploration of explicit data access sequences. As a proof of concept we analyze the TACLeBench benchmark suite, showing that most loads/stores present data reuse, and how compiler optimizations affect it. Using a simple hit/miss estimation on our reuse results, the time devoted to data accesses in the worst case is reduced to 27% compared to an always-miss system, equivalent to a data hit ratio of 81%. With compiler optimization, such time is reduced to 6.5%., This work was supported in part by MINECO/AEI/ERDF (EU) under Grant TIN2016-76635-C2-1-R, Grant TIN2017-86727-C2-1-R, and Grant PID2019-105660RB-C21; in part by the Aragón Government under Grant T58_20R research group; in part by the Generalitat de Catalunya under Grant 2017 SGR 786 and Grant FI-DGR 2015; and in part by the Construyendo Europa desde Aragón under Grant ERDF 2014-2020., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Learning random points from geometric graphs or orderings

  • Díaz Cort, Josep
  • Mcdiarmid, Colin
  • Mitsche, Dieter
Let Xv for v∈V be a family of n iid uniform points in the square (Formula presented.). Suppose first that we are given the random geometric graph (Formula presented.), where vertices u and v are adjacent when the Euclidean distance dE(Xu,Xv) is at most r. Let n3/14≪r≪n1/2. Given G (without geometric information), in polynomial time we can with high probability approximately reconstruct the hidden embedding, in the sense that “up to symmetries,” for each vertex v we find a point within distance about r of Xv; that is, we find an embedding with “displacement” at most about r. Now suppose that, instead of G we are given, for each vertex v, the ordering of the other vertices by increasing Euclidean distance from v. Then, with high probability, in polynomial time we can find an embedding with displacement (Formula presented.)., This research was supported by the grants GRAMM, TIN2017-86727-C2-1-R (J.D.), and by IDEXLYON of Université de Lyon (Programme Investissements d’Avenir, ANR16-IDEX-0005), and by LABEXMILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) (D.M.), Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Some results of Maria Serna on strategic games: Complexity of equilibria and models

  • Álvarez Faura, M. del Carme
  • Duch Brown, Amalia
We survey some recent work of Maria Serna concerning strategic games. We first examine some results related to the formal representation of strategic games and the complexity of problems related to both the existence of equilibria and the equivalence of games. These results provided a better understanding of how the succinctness of the game representation affects the complexity of such problems. We then describe some work dealing with the definition of new strategic games. The study of a Network Formation Game with asymmetric players, and the introduction of Celebrity Games as well as of Strategic Search Games intend to explain the natural behaviour of agents acting in some particular environments like communication networks, social networks, or even networks that contain valuable items hidden in different nodes., This work was partially supported by funds from the AGAUR, Spain of the Government of Catalonia under project ref. 2017 SGR 786 (ALBCOM), by the Spanish Ministry for Economy and Competitiveness (MINECO), Spain and by the European Union (FEDER funds), under grants ref. TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Anti-alignments—Measuring the precision of process models and event logs

  • Chatain, Thomas
  • Boltenhagen, Mathilde
  • Carmona Vargas, Josep
Processes are a crucial artifact in organizations, since they coordinate the execution of activities so that products and services are provided. The use of models to analyze the underlying processes is a well-known practice. However, due to the complexity and continuous evolution of their processes, organizations need an effective way of analyzing the relation between processes and models. Conformance checking techniques assess the suitability of a process model in representing an underlying process, observed through a collection of real executions. One important metric in conformance checking is to assess the precision of the model with respect to the observed executions, i.e., characterize the ability of the model to produce behavior unrelated to the one observed. In this paper we present the notion of anti-alignment as a concept to help unveiling runs in the model that may deviate significantly from the observed behavior. Using anti-alignments, a new metric for precision is proposed. The proposed anti-alignment based precision metric satisfies most of the required axioms highlighted in a recent publication. Moreover, a complexity analysis of the problem of computing anti-alignments is provided, which sheds light into the practicability of using anti-alignment to estimate precision. Experiments are provided that witness the validity of the concepts introduced in this paper., This work has been partially supported by funds from ENS Paris-Saclay, Spain (project ProMAut of the Farman institute), the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Robustness to voltage noise with ring oscillator clocks

  • Machado, Lucas
  • Roca Pérez, Antoni
  • Cortadella, Jordi
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Voltage noise is the main source of dynamic variability in integrated circuits and a major concern for the design of power delivery networks (PDNs). Lower supply voltages were made possible with technology scaling, but power density was also increased. Consequently, power integrity became a key factor in the design of reliable high performance circuits. Ring oscillators clocks (ROCs) have been proposed as an alternative to mitigate the negative effects of voltage noise. However, the effectiveness highly depends on the design parameters of the PDN, power consumption patterns, and spatial locality of the ROC within the clock domain. This paper analyzes the impact of the PDN parameters and ROC location on the voltage noise and the robustness achieved by using ROCs. The capability of reacting instantaneously to large voltage droops makes ROCs an attractive solution, which also allows to relax the constraints required for the PDN design. The experiments show that up to 83% of the margins for voltage noise and up to 27% of the total leakage power can be reduced by using ROCs. In addition, PDN simplifications are possible, with fewer power interconnections or package decoupling capacitors of lower quality. Tolerance to voltage noise and related benefits can be increased with multiple ROCs., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Dynamic pipelining of multidimensional range queries

  • Duch Brown, Amalia
  • Lugosi, Daniel
  • Pasarella Sánchez, Ana Edelmira
  • Zoltan Torres, Ana Cristina
The problem of evaluating orthogonal range queries efficiently has been studied widely in the data structures community. It has been common wisdom for several years that for queries containing more than 20% of the elements of the dataset a linear scanning of the data was the most efficient solution. In recent experimental works using modern hardware –with main memory and parallelism– the conclusion is that linear scan is preferable for almost every query configuration (even containing a 1% of the data). In this work we propose an alternative approach to evaluate multidimensional range queries based on the dynamic pipeline paradigm –using main memory and concurrency. Our aim is to prove that under this framework, it is possible to beat the performance of linear scanning by the one of hierarchical multidimensional data structures –such as kd trees, quad trees, Rtrees or similar., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Empowering conformance checking using Big Data through horizontal decomposition

  • Valencia Parra, Álvaro
  • Varela Vaca, Ángel Jesús
  • Gómez López, María Teresa
  • Carmona Vargas, Josep
  • Bergenthum, Robin
Conformance checking unleashes the full power of process mining: techniques from this discipline enable the analysis of the quality of a process model through the discovery of event data, the identification of potential deviations, and the projection of real traces onto process models. In this way, the insights gained from the available event data can be transferred to a richer conceptual level, amenable for human interpretation. Unfortunately, most of the aforementioned functionalities are grounded in an extremely difficult fundamental problem: given an observed trace and a process model, find the model trace that most closely resembles to the trace observed. This paper presents an architecture that supports the creation and distribution of alignment subproblems based on an innovative horizontal acyclic model decomposition, disengaged from the conformance checking algorithm applied for their solution. This is supported by a Big Data infrastructure that facilitates the customised distribution of a gross amount of data. Experiments are provided that testify to the enormous potential of the architecture proposed, thereby opening the door to further research in several directions., This work has been partially funded by the Ministry of Science and Technology of Spain ECLIPSE (RTI2018-094283-B-C33) project, the European Regional Development Fund (ERDF/FEDER), MINECO (TIN2017-86727-C2-1-R), and by the University of Seville with VI Plan Propio de Investigación y Transferencia (VI PPIT-US)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Bridging the gap between energy consumption and distribution through non-technical loss detection

  • Coma Puig, Bernat
  • Carmona Vargas, Josep
The application of Artificial Intelligence techniques in industry equips companies with new essential tools to improve their principal processes. This is especially true for energy companies, as they have the opportunity, thanks to the modernization of their installations, to exploit a large amount of data with smart algorithms. In this work we explore the possibilities that exist in the implementation of Machine-Learning techniques for the detection of Non-Technical Losses in customers. The analysis is based on the work done in collaboration with an international energy distribution company. We report on how the success in detecting Non-Technical Losses can help the company to better control the energy provided to their customers, avoiding a misuse and hence improving the sustainability of the service that the company provides., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Optimized SAT encoding of conformance checking artefacts

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep
Conformance checking is a growing discipline that aims at assisting organizations in monitoring their processes. On its core, conformance checking relies on the computation of particular artefacts which enable reasoning on the relation between observed and modeled behavior. It is widely acknowledge that the computation of these artifacts is the lion’s share of conformance checking techniques. This paper shows how important conformance artefacts like alignments, anti-alignments or multi-alignments, defined over the Levenshtein edit distance, can be efficiently computed by encoding the problem as an optimized SAT instance. From a general perspective, the work advocates for a unified family of techniques that can compute conformance artefacts in the same way. The implementation of the techniques presented in this paper show capabilities for dealing with both synthetic and real-life instances, which may open the door for a fresh way of applying conformance checking in the near future., This work has been supported by Farman institute at ENS Paris-Saclay and by MINECO and FEDER funds under Grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Maria Serna’s contributions to adversarial queuing theory

  • Blesa Aguilera, Maria Josep
  • Fernández Anta, Antonio
Adversarial Queuing Theory (aqt) is one of the areas to which Maria Serna has deeply contributed in her scientific career. Most of her research in this area took place during the lustrum 2001–2005, while advising the Ph.D. of Maria J. Blesa (2006) [1], and also in conjunction with other researchers. aqt is an adversarial model for the study of packet-switching communication networks under worst case conditions. In this model a fundamental concept is that of stability of a combination of network and packet scheduling protocol in front of an adversary that controls the arrival of packets. There is stability if the adversary cannot cause the number of packets in the network to grow unbounded. Maria’s contributions, summarized in this document, include results in the stability of networks and protocols, and the definition and study of aqt models with important new characteristics, like priorities, failures, or networks with different bandwidths and packet lengths. These results keep impacting the new research currently done in the aqt model., This research has been partially supported by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under project 2017 SGR 786 (ALBCOM) and by MINECO and FEDER funds under grant GRAMM (ref. TIN2017-86727-C2-1-R)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Conformance checking in UML artifact-centric business process models

  • Estañol Lamarca, Montserrat
  • Muñoz Gama, Jorge
  • Carmona Vargas, Josep
  • Teniente López, Ernest
Business artifacts have appeared as a new paradigm to capture the information required for the complete execution and reasoning of a business process. Likewise, conformance checking is gaining popularity as a crucial technique that enables evaluating whether recorded executions of a process match its corresponding model. In this paper, conformance checking techniques are incorporated into a general framework to specify business artifacts. By relying on the expressive power of an artifact-centric specification, BAUML, which combines UML state and activity diagrams (among others), the problem of conformance checking can be mapped into the Petri net formalism and its results be explained in terms of the original artifact-centric specification. In contrast to most existing approaches, ours incorporates data constraints into the Petri nets, thus achieving conformance results which are more precise. We have also implemented a plug-in, within the ProM framework, which is able to translate a BAUML into a Petri net to perform conformance checking. This shows the feasibility of our approach., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

State-based encoding of large asynchronous controllers

  • Martínez Moreno, Albert
  • Cortadella, Jordi
State encoding is one of the fundamental problems in the synthesis of asynchronous controllers. The requirement for a correct hazard-free implementation imposes severe constraints on the way encoding signals can be inserted in the specification of a controller. Even though some specification formalisms, such as Burst-mode machines or Signal Transition Graphs, enable to specify behaviors at the event level, the state encoding methods that provide the best good-quality solutions work at the state level. This imposes a severe limitation on the size of the controllers that can be handled by these methods. This paper proposes a method to solve the encoding problem for large asynchronous controllers using statebased methods. It is based on an iterative process of projection and re-composition that reduces the size specification by hiding signals, partially solves the encoding problem at the state level and re-composes the original specification using a synchronous product. The process iterates until all encoding conflicts have been solved. The method is proved to preserve the behavior of the specification (branching bisimilarity) and shown to be capable of providing good-quality solutions for controllers of more than 100 signals and 106 states., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the PoA conjecture: Trees versus biconnected components

  • Álvarez Faura, M. del Carme
  • Messegué Buisan, Arnau
In the classical model of network creation games introduced by Fabrikant et al. [Ona network creation game, in Proceedings of the Twenty-Second Annual Symposium on Principlesof Distributed Computing (PODC`03), 2003, pp. 347--351],nplayers correspond to the nodes of anetwork buying links of price\alpha and to the other players with the goal of being well-connected tothe resulting network. Still as an open problem, theconstantPoAconjecturestates that thePriceof Anarchy(PoA) is constant for any\alpha . When tackling this problem distinct behaviors must betaken into the account depending on whether\alpha has either large or low value. It is known that for\alpha >4n - 13 everyneis a tree and for\alpha =O(n1 - \delta ) with\delta \geq 1/lognthe diameter of networks thatare in equilibrium when restricting to deviations that consist only in buying links (buying equilibria)is at most a constant. These results imply that the PoA is constant for the disjoint union of thetwo ranges, and thus the constant PoA conjecture seems to be true for most of all the possiblevalues\alpha . In this paper we study the PoA for the remaining range of\alpha and we show the following:(i) For\alpha > n(1 +\epsilon ) the PoA is constant by proving that the size of any biconnected componentof an equilibrium graph is constant. (ii) For\alpha \leq n(1 +\epsilon ) we have that PoA = \Theta (dmax), wheredmaxis the maximum diameter of an equilibrium graph for the same range of\alpha . Therefore if theconstant PoA conjecture was false, it would suffice to construct equilibria of nonconstant diameter.Towards this direction we find nontrivialbuying equilibriaof nonconstant diameter when\alpha > n1 - \delta and\delta =O(2 - \surd \mathrm{l}\mathrm{o}\mathrm{g}n), exploring new intimate relationships betweendistance-uniform graphsandbuying equilibria., This work was partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R), from the European Union-NextGenerationEU under Margarita Salas, from UPC grant 2021UPC-MS-66935, and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786., Peer Reviewed, Postprint (published version), This work is the extended version of the conference paper ``On the Price of Anarchy for High-Price Links"" from Web and Internet Economics 15thInternational Conference, WINE 2019, New York, NY, 2019, Proceedings.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Supporting the process of learning and teaching process models

  • Sànchez-Ferreres, Josep
  • Delicado Alcántara, Luis
  • Andaloussi, Amine Abbad
  • Burattin, Andrea
  • Calderón Ruiz, Guillermo
  • Weber, Barbara
  • Carmona Vargas, Josep
  • Padró, Lluís
The creation of a process model faces the challenge of constructing a syntactically correct entity which accurately reflects the semantics of the reality, and is understandable. This paper proposes a framework called ModelJudge , focused towards the two main actors in the process of learning process model creation: novice modellers and instructors. For modellers, the platform enables the automatic validation of the process models created from the textual description, providing explanations about quality issues in the model. ModelJudge can provide diagnostics regarding model structure, writing style, and seman- tics by aligning annotated textual descriptions to models. For instructors, the platform facilitates the creation of modelling exercises by providing an editor to annotate the main parts of a textual description, that is empowered with Natural Language Processing (NLP) capabilities so that the annotation effort is minimized. So far around 300 students, in process modelling courses of five different universities around the world have used the platform. The feedback gathered from some of these courses shows good potential in helping students to improve their learning experience, which might, in turn, impact process model quality and understandability. Moreover, our results show that instructors can benefit from getting insights into the evolution of modeling processes including arising quality issues of single students, but also discover tendencies in groups of students. Although the framework has been applied to process model creation, it could be extrapolated to other contexts where the creation of models based on a textual description plays an important role., This work has been partially supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Algorithmically efficient syntactic characterization of possibility domains

  • Díaz Cort, Josep
  • Kirousis, Lefteris
  • Kokonezi, Sofia
  • Livieratos, John
In the field of Judgment Aggregation, a domain, that is a subset of a Cartesian power of {0, 1}, is considered to reflect abstract rationality restrictions on vectors of two-valued judgments on a number of issues. We are interested in the ways we can aggregate the positions of a set of individuals, whose positions over each issue form vectors of the domain, by means of unanimous (idempotent) functions, whose output is again an element of the domain. Such functions are called non-dictatorial, when their output is not simply the positions of a single individual. Here, we consider domains admitting various kinds of non-dictatorial aggregators, which reflect various properties of majority aggregation: (locally) non-dictatorial, generalized dictatorships, anonymous, monotone, StrongDem and systematic. We show that interesting and, in some sense, democratic voting schemes are always provided by domains that can be described by propositional formulas of specific syntactic types we define. Furthermore, we show that we can efficiently recognize such formulas and that, given a domain, we can both efficiently check if it is described by such a formula and, in case it is, construct it. Our results fall in the realm of classical results concerning the syntactic characterization of domains with specific closure properties, like domains closed under logical AND which are the models of Horn formulas. The techniques we use to obtain our results draw from judgment aggregation as well as propositional logic and universal algebra., The first two authors’ research was partially supported by TIN2017-86727-C2-1-R, GRAMM. The research of the second author was carried out while visiting the Computer Science Department of the Universitat Politècnica de Catalunya., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Multi-level dataflow-driven macro placement guided by RTL structure and analytical methods

  • Vidal Obiols, Alexandre
  • Cortadella, Jordi
  • Petit Silvestre, Jordi
  • Galcerán Oms, Marc
  • Martorell Cid, Ferran
When RTL designers define the hierarchy of a system, they exploit their knowledge about the conceptual abstractions devised during the design and the functional interactions between the logical components. This valuable information is often lost during physical synthesis. This paper proposes HiDaP, a novel multi-level algorithm that uses RTL information and analytical methods for the macro placement problem of modern designs dominated by multi-cycle connection pipelines. By taking advantage of the hierarchy tree, the netlist is divided into blocks containing macros and standard cells, and their dataflow affinity is inferred considering the register latency and flow width of their interaction. The layout is represented using slicing structures and generated with a top-down algorithm capable of handling blocks with both hard and soft components. An adaptive multi-objective cost function is used to simultaneously minimize wirelength, timing, overlap and distance to preferred locations, which can be user-defined or generated by analytic methods (spectral and force-directed). These techniques have been applied to a set of large industrial circuits and compared against state-of-theart commercial and academic placers, and also to handcrafted floorplans generated by expert back-end engineers. The proposed approach outperforms previous algorithmic methods and can produce solutions with better wirelength and timing than the best handcrafted floorplans. Post-routing layouts are almost brought to timing closure and DRC cleanness with minimal engineer modification, showing that the generated floorplans provide an excellent starting point for the physical design flow and contribute to reduce turn-around time significantly., This work has been partially supported by a grant from Inphi Corporation and funds from the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER funds) under grant TIN2017-86727-C2-1-R, and the Generalitat de Catalunya (2017 SGR 786)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Satisfaction and power in unanimous majority influence decision models

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
We consider decision models associated with cooperative influence games, the oblivious and the non-oblivious influence models. In those models the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures when the in uence level is set to unanimity and the rule of decision is simple majority. We show that computing the satisfaction and the power measure in those systems are #P-hard., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Flexible process model mapping using relaxation labeling

  • Delicado Alcántara, Luis
  • Carmona Vargas, Josep
  • Padró, Lluís
Computing a mapping between two process models is a crucial technique, since it enables reasoning and operating across processes, like providing a similarity score between two processes, or merging different process variants to generate a consolidated process model. In this paper we present a new flexible technique for process model mapping, based on the relaxation labeling constraint satisfaction algorithm. The technique can be instantiated so that different modes are devised, depending on the context. For instance, it can be adapted to the case where one of the mapped process models is incomplete, or it can be used to ground an adaptable similarity measure between process models. The approach has been implemented inside the open platform NLP4BPM, providing a visualization of the performed mappings and computed similarity scores. The experimental results witness the flexibility and usefulness of the technique proposed., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Model-based trace variant analysis of event logs

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep
The comparison of trace variants of business processes opens the door for a fine-grained analysis of the distinctive features inherent in the executions of a process in an organization. The current approaches for trace variant analysis do not consider the situation where a process model is present, and therefore, it can guide the derivation of the trace variants by considering high-level structures present in the process model. In this paper we propose a fresh alternative to trace variant analysis, which proposes a generalized notion of trace variant that incorporates concurrency and iteration. This way, the analyst may be relieved from analyzing trace variants that are essentially the same, if these aspects are disregarded. We propose a general algorithm for model based trace variant analysis which is grounded in encoding the problem into SAT, and a family of heuristic alternatives including a very light sampling technique that represents a good trade-off between quality of the trace variants identified, and the complexity of the analysis. All the techniques of the paper are implemented in two open-source tools, and experiments with publicly available benchmarks are reported., This work has been supported by Farman institute at ENS Paris-Saclay, Spain and by MINECO, Spain and FEDER, Spain funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Automated repair of process models with non-local constraints using state-based region theory

  • Kalenkova, Anna
  • Carmona Vargas, Josep
  • Polyvyanyy, Artem
  • La Rosa, Marcello
State-of-the-art process discovery methods construct free-choice process models from event logs. Consequently, the constructed models do not take into account indirect dependencies between events. Whenever the input behaviour is not free-choice, these methods fail to provide a precise model. In this paper, we propose a novel approach for enhancing free-choice process models by adding non-free-choice constructs discovered a-posteriori via region-based techniques. This allows us to benefit from the performance of existing process discovery methods and the accuracy of the employed fundamental synthesis techniques. We prove that the proposed approach preserves fitness with respect to the event log while improving the precision when indirect dependencies exist. The approach has been implemented and tested on both synthetic and real-life datasets. The results show its effectiveness in repairing models discovered from event logs., This work was partly supported by the Australian Research Council Discovery Project DP180102839. This work was supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Computation of alignments of business processes through relaxation labelling and local optimal search

  • Padró, Lluís
  • Carmona Vargas, Josep
A fundamental problem in conformance checking is aligning event data with process models. Unfortunately, existing techniques for this task are either complex, or can only be applicable to restricted classes of models. This in practice means that for large inputs, current techniques often fail to produce a result. In this paper we propose a method to compute alignments for unconstrained process models, which relies on the use of relaxation labelling techniques on top of a partial order representation of the process model. The technique proposed in this paper precomputes information used in the search for alignments, and is able to produce real alignments that may be close to optimal ones by combining the aforementioned techniques with a locally applied A strategy. Remarkably, the implementation on the proposed technique achieves a speed-up of several orders of magnitude with respect to the approaches in the literature (either optimal, sup-optimal or approximate), often with a reasonable trade-off on the cost of the obtained alignment., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A tour in process mining: from practice to algorithmic challenges

  • Van der Aalst, Wil M.P.
  • Carmona Vargas, Josep
  • Chatain, Thomas
  • Dongen, Boudewijn F. van
Process mining seeks the confrontation between modeled behavior and observed behavior. In recent years, process mining techniques managed to bridge the gap between traditional model-based process analysis (e.g., simulation and other business process management techniques) and data-centric analysis techniques such as machine learning and data mining. Process mining is used by many data-driven organizations as a means to improve performance or to ensure compliance. Traditionally, the focus was on the discovery of process models from event logs describing real process executions. However, process mining is not limited to process discovery and also includes conformance checking. Process models (discovered or hand-made) may deviate from reality. Therefore, we need powerful means to analyze discrepancies between models and logs. These are provided by conformance checking techniques that first align modeled and observed behavior, and then compare both. The resulting alignments are also used to enrich process models with performance related information extracted from the event log. This tutorial paper focuses on the control-flow perspective and describes a range of process discovery and conformance checking techniques. The goal of the paper is to show the algorithmic challenges in process mining. We will show that process mining provides a wealth of opportunities for people doing research on Petri nets and related models of concurrency., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

CNN-on-AWS: Efficient allocation of multikernel applications on Multi-FPGA platforms

  • Shan, Junnan
  • Lazarescu, Mihai T.
  • Cortadella, Jordi
  • Lavagno, Luciano
  • Casu, Mario R.
Multi-FPGA platforms, like Amazon AWS F1, can run in the cloud multikernel pipelined applications, like convolutional neural networks (CNNs), with excellent performance and lower energy consumption than CPUs or GPUs. We propose a method to efficiently map these applications on multi-FPGA platforms to maximize the application throughput. Our methodology finds, for the given resources, the optimal number of parallel instances of each kernel in the pipeline and their allocation to one or more among the available FPGAs. We obtain this by formulating and solving a mixed-integer, nonlinear optimization problem, in which we model the performance of each component and the duration of the phases in which the accelerated computation can be split into, namely: 1) data transfer from a host CPU to the DDR memory of each FPGA; 2) data transfer from FPGA DDR to FPGA on-chip memory; 3) kernel computation on the FPGA; 4) data transfer from FPGA on-chip memory to FPGA DDR; and 5) data transfer from FPGA DDR to host. Finding the optimal solution using a mixed-integer nonlinear programming (MINLP) solver is often highly inefficient. Hence, we provide a fast heuristic method that according to our experiments can be much more efficient than the MINLP solver and finds comparable results. For larger problems (more CNN layers), our heuristic method can quickly find (several thousand times faster) much better solutions than the MINLP solver, even if we run the latter for a very long time., This work was supported in part by the European Commission through the ECOSCALE Project under Grant H2020-ICT671632, in part by the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER funds) under Grant TIN2017-86727-C2-1-R and Grant FPI 2015, and in part by the Generalitat de Catalunya under Grant 2017 SGR 786., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A navigational logic for reasoning about graph properties

  • Navarro Gómez, Marisa
  • Orejas Valdés, Fernando
  • Pino Blanco, Elvira
  • Lambers, Leen
Graphs play an important role in many areas of Computer Science. In particular, our work is motivated by model-driven software development and by graph databases. For this reason, it is very important to have the means to express and to reason about the properties that a given graph may satisfy. With this aim, in this paper we present a visual logic that allows us to describe graph properties, including navigational properties, i.e., properties about the paths in a graph. The logic is equipped with a deductive tableau method that we have proved to be sound and complete., This work was supported by the Spanish Ministry of Economy and Competitiveness and the European Union (FEDER funds) under grant GRAMM (ref. TIN2017-86727-C2-1-R, TIN2017-86727-C2-2-R) and by the Basque Project GIU15/30, and grant UFI11/45., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Unleashing textual descriptions of business processes

  • Sànchez-Ferreres, Josep
  • Burattin, Andrea
  • Carmona Vargas, Josep
  • Montali, Marco
  • Padró, Lluís
  • Quishpi Betún, Luis Hernán
Textual descriptions of processes are ubiquitous in organizations, so that documentation of the important processes can be accessible to anyone involved. Unfortunately, the value of this rich data source is hampered by the challenge of analyzing unstructured information. In this paper we propose a framework to overcome the current limitations on dealing with textual descriptions of processes. This framework considers extraction and analysis and connects to process mining via simulation. The framework is grounded in the notion of annotated textual descriptions of processes, which represents a middle-ground between formalization and accessibility, and which accounts for different modeling styles, ranging from purely imperative to purely declarative. The contributions of this paper are implemented in several tools, and case studies are highlighted., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)