Spelling suggestions: "subject:"informática"" "subject:"informatica""
121 |
Efficient hardware/software co-designed schemes for low-power processorsLópez Muñoz, Pedro 17 March 2014 (has links)
Nowadays, we are reaching a point where further improving single thread performance can only be done at the expenses of significantly increasing power consumption. Thus, multi-core chips have been adopted by the industry and the scientific community as a proven solution to improve performance with limited power consumption. However, the number of units to be integrated into a single die is limited by its area and power restrictions, and therefore the thread level parallelism (TLP) that could be exploited is also limited. One way to continue incrementing the number of core units is to reduce the complexity of each individual core at the cost of sacrificing instruction level parallelism (ILP). We face a design trade-off here: to dedicate the total available die area to put a lot of simple cores and favor TLP or to dedicate it to put fewer cores and favor ILP. Among the different solutions already studied in the literature to deal with this challenge, we selected hybrid hardware/software co-designed processors. This solution provides high single thread performance on simple low-power cores through a software dynamic binary optimizer tightly coupled with the hardware underneath. For this reason, we believe that hardware/software co-designed processors is an area that deserves special attention on the design of multi-core systems since it allows implementing multiple simple cores suitable to maximize TLP but sustaining better ILP than conventional pure hardware approaches. In particular, this thesis explores three different techniques to address some of the most relevant challenges on the design of a simple low-power hardware/software co-designed processor.
The first technique is a profiling mechanism, named as LIU Profiler, able to detect hot code regions. It consists in a small hardware table that uses a novel replacement policy aimed at detecting hot code. Such simple hardware structure implements this mechanism and allows the software to apply heuristics when building code regions and applying optimizations. The LIU Profiler achieves 85.5% code coverage detection whereas similar profilers implementing traditional replacement policies reach up to 60% coverage requiring a 4x bigger table. Moreover, the LIU Profiler only increases by 1% the total area of a simple low-power processor and consumes less than 0.87% of the total processor power. The LIU Profiler enables improving single thread performance without significantly incrementing the area and power of the processor.
The second technique is a rollback scheme aimed to support code reordering and aggressive speculative optimizations on hot code regions. It is named HRC and combines software and hardware mechanisms to checkpoint and to recover the architectural register state of the processor. When compared with pure hardware solutions that require doubling the number of registers, the proposal reduces by 11% the area of the processor and by 24.4% the register file power consumption, at the cost of only degrading 1% the performance.
The third technique is a loop parallelization (LP) scheme that uses the software layer to dynamically detect loops of instructions and to prepare them to execute multiple iterations in parallel by using Simultaneous Multi-Threading threads. These are optimized by employing dedicated loop parallelization binary optimizations to speed-up loop execution. LP scheme uses novel fine-grain register communication and thread dynamic register binding technique, as well as already existing processor resources. It introduces small overheads to the system and even small loops and loops that iterate just a few times are able to get significant performance improvements. The execution time of the loops is improved by more than a 16.5% when compared to a fully optimized baseline. LP contributes positively to the integration of a high number of simple cores in the same die and it allows those cores to cooperate to some extent to continue exploiting ILP when necessary.
|
122 |
AUGURES : profit-aware web infrastructure managementPoggi M., Nicolas 07 May 2014 (has links)
Over the last decade, advances in technology together with the increasing use of the Internet for everyday tasks, are causing profound changes in end-users, as well as in businesses and technology providers. The widespread adoption of high-speed and ubiquitous Internet access, is also changing the way users interact with Web applications and their expectations in terms of Quality-of-Service (QoS) and User eXperience (UX). Recently, Cloud computing has been rapidly adopted to host and manage Web applications, due to its inherent cost effectiveness and on-demand scaling of infrastructures. However, system administrators still need to make manual decisions about the parameters that affect the business results of their applications ie., setting QoS targets and defining metrics for scaling the number of servers during the day. Therefore, understanding the workload and user behavior ¿the demand, poses new challenges for capacity planning and scalability ¿the supply, and ultimately for the success of a Web site.
This thesis contributes to the current state-of-art of Web infrastructure management by providing: i) a methodology for predicting Web session revenue; ii) a methodology to determine high response time effect on sales; and iii) a policy for profit-aware resource management, that relates server capacity, to QoS, and sales. The approach leverages Machine Learning (ML) techniques on custom, real-life datasets from an Ecommerce retailer featuring popular Web applications. Where the experimentation shows how user behavior and server performance models can be built from offline information, to determine how demand and supply relations work as resources are consumed. Producing in this way, economical metrics that are consumed by profit-aware policies, that allow the self-configuration of cloud infrastructures to an optimal number of servers under a variety of conditions. While at the same time, the thesis, provides several insights applicable for improving Autonomic infrastructure management and the profitability of Ecommerce applications. / Durante la última década, avances en tecnología junto al incremento de uso de Internet, están causando cambios en los usuarios finales, así como también a las empresas y proveedores de tecnología. La adopción masiva del acceso ubicuo a Internet de alta velocidad, crea cambios en la forma de interacción con las aplicaciones Web y en las expectativas de los usuarios en relación de calidad de servicio (QoS) y experiencia de usuario (UX) ofrecidas. Recientemente, el modelo de computación Cloud ha sido adoptado rápidamente para albergar y gestionar aplicaciones Web, debido a su inherente efectividad en costos y servidores bajo demanda. Sin embargo, los administradores de sistema aún tienen que tomar decisiones manuales con respecto a los parámetros de ejecución que afectan a los resultados de negocio p.ej. definir objetivos de QoS y métricas para escalar en número de servidores. Por estos motivos, entender la carga y el comportamiento de usuario (la demanda), pone nuevos desafíos a la planificación de capacidad y escalabilidad (el suministro), y finalmente el éxito de un sitio Web.Esta tesis contribuye al estado del arte actual en gestión de infraestructuras Web presentado: i) una metodología para predecir los beneficios de una sesión Web; ii) una metodología para determinar el efecto de tiempos de respuesta altos en las ventas; y iii) una política para la gestión de recursos basada en beneficios, al relacionar la capacidad de los servidores, QoS, y ventas. La propuesta se basa en aplicar técnicas Machine Learning (ML) a fuentes de datos de producción de un proveedor de Ecommerce, que ofrece aplicaciones Web populares. Donde los experimentos realizados muestran cómo modelos de comportamiento de usuario y de rendimiento de servidor pueden obtenerse de datos históricos; con el fin de determinar la relación entre la demanda y el suministro, según se utilizan los recursos. Produciendo así, métricas económicas que son luego aplicadas en políticas basadas en beneficios, para permitir la auto-configuración de infraestructuras Cloud a un número adecuado de servidores. Mientras que al mismo tiempo, la tesis provee información relevante para mejorar la gestión de infraestructuras Web de forma autónoma y aumentar los beneficios en aplicaciones de Ecommerce.
|
123 |
Non-functional requirements as drivers of software architecture designAmeller, David 23 January 2014 (has links)
In the last decades, software engineering has become an important area of research. As researchers, we try to identify a problem, a need, or a hole in some research topic, once identified we make an effort to produce new techniques, methods, and tools that hopefully will help to improve the detected issue. In the present thesis the identified issue was the need of supporting non-functional requirements in the software architecture design where these requirements are the drivers of the architectural decision-making.
This thesis started with the idea that a relatively new software engineering discipline, model-driven development, was a good place to propose a solution for the detected issue. We envisioned how non-functional requirements can be integrated in model-driven development and how this integration will impact in the architectural design activities.
When we started to produce our techniques, methods, and tools for model-driven development we found out that there was a bigger hole in the web of knowledge than what we had initially foreseen. Much of the evidence of how non-functional requirements affect the software architecture design is hidden. This situation caused a turn in this thesis: we needed to understand architects, how they think and how they make the architectural decisions, what is the role of non-functional requirements in the architectural decision-making process, and to what extent are the non-functional requirements important in this process. All these questions needed an answer, an answer that only architects could provide. In consequence we opted to drove several empirical studies to answer these questions.
In parallel, we started to work in a way of representing this knowledge, an ontology for software architecture that integrates non-functional requirements. Using this ontology as basis, we designed a method to assist architects in the architectural decision-making process and a tool that acted as a proof of concept of both, the ontology and the method.
In summary, this thesis explores how non-functional requirements are currently integrated in the software architecture design practices, and proposes ways to improve this integration and facilitate the work of architects by providing means to assist them in the architectural decision-making process.
|
124 |
Skeletal representations of orthogonal shapesMartínez Bayona, Jonàs 12 December 2013 (has links)
Skeletal representations are important shape descriptors which encode topological and geometrical properties of shapes and reduce their dimension. Skeletons are used in several fields of science and attract the attention of many researchers. In the biocad field, the analysis of structural properties such as porosity of biomaterials requires the previous computation of a skeleton. As the size of three-dimensional images become larger, efficient and robust algorithms that extract simple skeletal structures are required. The most popular and prominent skeletal representation is the medial axis, defined as the shape points which have at least two closest points on the shape boundary. Unfortunately, the medial axis is highly sensitive to noise and perturbations of the shape boundary. That is, a small change of the shape boundary may involve a considerable change of its medial axis. Moreover, the exact computation of the medial axis is only possible for a few classes of shapes. For example, the medial axis of polyhedra is composed of non planar surfaces, and its accurate and robust computation is difficult. These problems led to the emergence of approximate medial axis representations. There exists two main approximation methods: the shape is approximated with another shape class or the Euclidean metric is approximated with another metric.
The main contribution of this thesis is the combination of a specific shape and metric simplification. The input shape is approximated with an orthogonal shape, which are polygons or polyhedra enclosed by axis-aligned edges or faces, respectively. In the same vein, the Euclidean metric is replaced by the L infinity or Chebyshev metric. Despite the simpler structure of orthogonal shapes, there are few works on skeletal representations applied to orthogonal shapes. Much of the efforts have been devoted to binary images and volumes, which are a subset of orthogonal shapes. Two new skeletal representations based on this paradigm are introduced: the cube skeleton and the scale cube skeleton. The cube skeleton is shown to be composed of straight line segments or planar faces and to be homotopical equivalent to the input shape. The scale cube skeleton is based upon the cube skeleton, and introduces a family of skeletons that are more stable to shape noise and perturbations. In addition, the necessary algorithms to compute the cube skeleton of polygons and polyhedra and the scale cube skeleton of polygons are presented. Several experimental results confirm the efficiency, robustness and practical use of all the presented methods.
|
125 |
Raising the level of abstraction : simulation of large chip multiprocessors running multithreaded applicationsRico Carro, Alejandro 29 October 2013 (has links)
The number of transistors on an integrated circuit keeps doubling every two years. This increasing number of transistors is used to integrate more processing cores on the same chip. However, due to power density and ILP diminishing returns, the single-thread performance of such processing cores does not double every two years, but doubles every three years and a half.
Computer architecture research is mainly driven by simulation. In computer architecture simulators, the complexity of the simulated machine increases with the number of available transistors. The more transistors, the more cores, the more complex is the model. However, the performance of computer architecture simulators depends on the single-thread performance of the host machine and, as we mentioned before, this is not doubling every two years but every three years and a half. This increasing difference between the complexity of the simulated machine and simulation speed is what we call the simulation speed gap.
Because of the simulation speed gap, computer architecture simulators are increasingly slow. The simulation of a reference benchmark may take several weeks or even months. Researchers are concious of this problem and have been proposing techniques to reduce simulation time. These techniques include the use of reduced application input sets, sampled simulation and parallelization.
Another technique to reduce simulation time is raising the level of abstraction of the simulated model. In this thesis we advocate for this approach. First, we decide to use trace-driven simulation because it does not require to provide functional simulation, and thus, allows to raise the level of abstraction beyond the instruction-stream representation.
However, trace-driven simulation has several limitations, the most important being the inability to reproduce the dynamic behavior of multithreaded applications. In this thesis we propose a simulation methodology that employs a trace-driven simulator together with a runtime sytem that allows the proper simulation of multithreaded applications by reproducing the timing-dependent dynamic behavior at simulation time.
Having this methodology, we evaluate the use of multiple levels of abstraction to reduce simulation time, from a high-speed application-level simulation mode to a detailed instruction-level mode. We provide a comprehensive evaluation of the impact in accuracy and simulation speed of these abstraction levels and also show their applicability and usefulness depending on the target evaluations. We also compare these levels of abstraction with the existing ones in popular computer architecture simulators. Also, we validate the highest abstraction level against a real machine.
One of the interesting levels of abstraction for the simulation of multi-cores is the memory mode. This simulation mode is able to model the performanceof a superscalar out-of-order core using memory-access traces. At this level of abstraction, previous works have used filtered traces that do not include L1 hits, and allow to simulate only L2 misses for single-core simulations. However, simulating multithreaded applications using filtered traces as in previous works has inherent inaccuracies. We propose a technique to reduce such inaccuracies and evaluate the speed-up, applicability, and usefulness of memory-level simulation.
All in all, this thesis contributes to knowledge with techniques for the simulation of chip multiprocessors with hundreds of cores using traces. It states and evaluates the trade-offs of using varying degress of abstraction in terms of accuracy and simulation speed.
|
126 |
Improving the effective use of multithreaded architectures : implications on compilation, thread assignment, and timing analysisRadojković, Petar 19 July 2013 (has links)
This thesis presents cross-domain approaches that improve the effective use of multithreaded architectures. The contributions of the thesis can be classified in three groups. First, we propose several methods for thread assignment of network applications running in multithreaded network servers. Second, we analyze the problem of graph partitioning that is a part of the compilation process of multithreaded streaming applications. Finally, we present a method that improves the measurement-based timing analysis of multithreaded architectures used in time-critical environments. The following sections summarize each of the contributions.
(1) Thread assignment on multithreaded processors: State-of-the-art multithreaded processors have different level of resource sharing (e.g. between thread running on the same core and globally shared resources). Thus, the way that threads of a given workload are assigned to processors' hardware contexts determines which resources the threads share, which, in turn, may significantly affect the system performance.
In this thesis, we demonstrate the importance of thread assignment for network applications running in multithreaded servers. We also present TSBSched and BlackBox scheduler, methods for thread assignment of multithreaded network applications running on processors with several levels of resource sharing. Finally, we propose a statistical approach to the thread assignment problem. In particular, we show that running a sample of several hundred or several thousand random thread assignments is sufficient to capture at least one out of 1% of the best-performing assignments with a very high probability. We also describe the method that estimates the optimal system performance for given workload. We successfull y applied TSBSched, BlackBox scheduler, and the presented statistical approach to a case study of thread assignment of multithreaded network applications running on the UltraSPARC T2 processor.
(2) Kernel partitioning of streaming applications: An important step in compiling a stream program to multiple processors is kernel partitioning. Finding an optimal kernel partition is, however, an intractable problem. We propose a statistical approach to the kernel partitioning problem. We describe a method that statistically estimates the performance of the optimal kernel partition. We demonstrate that the sampling method is an important part of the analysis, and that not all methods that generate random samples provide good results. We also show that random sampling on its own can be used to find a good kernel partition, and that it could be an alternative to heuristics-based approaches. The presented statistical method is applied successfully to the benchmarks included in the StreamIt 2.1.1 suite.
(3) Multithreaded processors in time-critical environments: Despite the benefits that multithreaded commercial-of-the-shelf (MT COTS) processors may offer in embedded real-time systems, the time-critical market has not yet embraced a shift toward these architectures. The main challenge with MT COTS architectures is the difficulty when predicting the execution time of concurrently-running (co-running) time-critical tasks. Providing a timing analysis for real industrial applications running on MT COTS processors becomes extremely difficult because the execution time of a task, and hence its worst-case execution time (WCET) depends on the interference with co-running tasks in shared processor resources. We show that the measurement-based timing analysis used for single-threaded processors cannot be directly extended for MT COTS architectures. Also, we propose a methodology that quantifies the slowdown that a task may experience because of collision with co-running tasks in shared resources of MT COTS processor. The methodology is applied to a case study in which different time-critical applications were executed on several MT COTS multithreaded processors.
|
127 |
A Dynamic Validation Infrastructure for Interoperable Grid ServicesLuna García, Jesús 05 May 2008 (has links)
Los encargados de recursos Grid pueden autorizar el acceso a sus elementos de cómputo por medio de procedimientos bien establecidos para los clientes, regularmente a través del uso de credenciales criptográficas que en su mayoría tienen un tiempo de vida definido.A pesar que la adopción de Autoridades de Certificación -AC- ha parcialmente resuelto el problema de identificación y autenticación entre entidades y, la tecnología PKI (Infraestructuras de Clave Pública) es bastante madura, no es posible hacer los mismos supuestos cuando existen dominios que no confían entre si. En los últimos años han proliferado las Organizaciones Virtuales -VOs- dentro del Grid, cada una instalando su propia Autoridad de Certificación y dando lugar a un gran número de diferentes dominios de seguridad, que efectivamente no confían entre si. Esto da lugar a un complejo escenario de interoperabilidad en Grid, que requiere mecanismos capaces de determinar si una credencial cliente puede ser confiada en un momento dado. Este proceso (llamado "validacion") ha sido tradicionalmente tratado via Listas de Revocación de Certificados (CRLs). Sin embargo, esta solución es ineficiente tanto para la ACs como para las aplicaciones Grid. En consecuencia son requeridos mecanismos mas eficientes que permitan conocer el estado de un certificado en tiempo real. Entre estas soluciones, el Online Certificate Status Protocol (OCSP) sobresale para los Grids. A pesar de su importancia para la seguridad, OCSP conlleva considerables retos para el Grid y de momento es incapaz para garantizar un grado seguro de interoperabilidad entre las ACs que participan en dicho ambiente.De momento la comunidad Grid ha resuelto el problema de interoperabilidad mediante el uso de "Policy Management Authorities" (PMAs), las cuales representan "Federaciones de Grid-PKIs" cuyas ACs miembros cumplen con niveles mínimos de seguridad. Estos requisitos mínimos forman el llamado "Perfil de Autenticación de la PMA". Actualmente el cumplimiento con el perfil de una cierta PMA se lleva a cabo a través de un proceso bien definido, pero manual, que se realiza una sola ocasión cuando una AC desea ser parte de dicha PMA. Esto se denomina "Proceso de Acreditación".Cualquier cliente invocando una operación de un servicio Grid, activa un proceso de autenticación que valida su certificado digital de acuerdo a un proceso llamado "Path Validation".Cuando las ACs participantes interoperan gracias a acuerdos explícitos de confianza, solamente se require un "Path Validation Básico": verificación criptográfica y chequeo del estado del certificado. Software Grid como el Globus Toolkit, provee mecanismos estáticos para dicho proceso. Esto sin embargo resulta inapropiado para VOs actuales.Asi pues, a pesar de la importancia que un proceso automático y "Extendido" de "Path Validation" tendría para construir relaciones de confianza dinámicamente en Grid-PKIs, a la fecha no existe ningún mecanismo para hacerlo.Esta tesis presenta una arquitectura novedosa para llevar a cabo el proceso "Extendido de Path Validation" en ambientes Grid para ACs que pertenecen a la misma PMA, gracias al uso de una Infraestructura de Validación basada en el Grid-OCSP y, una metodología de evaluación de políticas que compara las Políticas de Certificación de las ACs involucradas para asegurarse que cumplen con un Perfil de Autenticación y, que por lo tanto pueden interoperar entre ellas. La metodología de evaluación de políticas está basada en una propuesta de investigación de la "Universidad de Nápoles, Federico II" y la "Segunda Universidad de Nápoles". Un prototipo de la Infraestructura de Validación ha sido desarrollado durante nuestra investigación, y es ampliamente explicado en esta tesis. / Grid Resource owners can authorize access to their computing elements by means of well established Authentication and Authorization processes for End-entities, through the use of cryptographic credentials that in most of the cases have a defined lifetime. Nevertheless, despite the fact that the adoption of Certification Authorities -CAs- has partially solved the problem of identification and authentication between the involved parties, and that Public Key Infrastructure -PKI- technologies are mature enough, we cannot make the same assumptions when untrusted domains are involved. In the last years a lot of Grid Virtual Organizations -VOs- have been proliferating, each one usually installing its own Certificate Authority and thus giving birth to a large set of different and possibly untrusted security domains. This brings a quite complex Grid interoperability scenario requiring mechanisms able to determine whether a particular end-entity's credential can be trusted at a given moment. This process is commonly named validation and traditionally it is performed via Certificate Revocation Lists (CRL). However this solution tends to be cumbersome for both, the CA and the application. In consequence, more efficient mechanisms to allow for the provision of real time certificate status information are required. Among these solutions, the Online Certificate Status Protocol (OCSP) stands out in the Grid community. Despite its importance for security, OCSP not only faces considerable challenges in the computational Grid but also, in its current form, this protocol is unable to guarantee a secure degree of interoperability among all the involved Grid-Certification Authorities. At the state of the art, the Grid community is circumventing the interoperability problem with the "Policy Management Authorities (PMAs)", which represent "Federations of Grid PKIs" whose CA members accomplish minimum levels of security. These minimum requirements comprise the PMA's Authentication Profile. In the case of the existing Grid PMAs, compliance with their respective authentication profile is given through a well-defined, but manual process involving a careful analysis of the applicant PKI's Certification Policy -CP-, performed just once, when a new CA wishes to be part of an existing PMA. This is known as the PMA's accreditation process.Any end-entity invoking a Grid Service's operation from the server, activates an authentication process that validates the end-entity's digital certificate according to the traditional path validation procedure.When involved CAs interoperate thanks to explicit trust agreements, only basic path validation is required: cryptographic verifications and status' checks over the involved certificates. State of the art Grid software like the Globus Toolkit, provides static mechanisms for the basic path validation. This is a cumbersome process in nowadays Virtual Organizations.Therefore, despite the importance that an automated and extended path validation process has got in order to build dynamic trust relationships among Grid PKI's, to date there is no mechanism to automatically obtain this information.This thesis presents a novel architecture for enabling extended path validation in Grid environments for CAs that are part of the same PMA, thanks to the use of a Validation Infrastructure based on a Grid-enabled Online Certificate Status Protocol and, a policy evaluation methodology that compares the involved CAs' Certificate Policies to assert that they fulfil with a particular Authentication Profile and that they can therefore interoperate among them. The policy evaluation technique is based on a formal methodology originally proposed by researchers of the "Università di Napoli, Federico II" and the "Seconda Università di Napoli". A working prototype of the proposed Validation Infrastructure was also developed during our research, and is widely explained along this thesis.
|
128 |
Design and evaluation of tridiagonal solvers for vector and parallel computersLarriba Pey, Josep Lluís 10 March 1995 (has links)
No description available.
|
129 |
Aprendizaje de particiones difusas para razonamiento inductivoAcosta Sarmiento, Jesús Antonio 22 December 2006 (has links)
Existe consenso entre los investigadores en que se pueden obtener sistemas más inteligentes por medio de la hibridación de metodologías de Soft Computing haciendo de este modo que las debilidades de unos sistemas se compensen con las bondades de otros. Los Sistemas Neurodifusos (SNDs) y los Sistemas Difusos Evolutivos (SDEs) constituyen la más notoria representatividad. Un Sistema Difuso Evolutivo es básicamente un sistema difuso robustecido por un proceso de aprendizaje basado en un Algoritmo Evolutivo (AE), en particular los Algoritmos Genéticos (AGs), los cuales están considerados actualmente como la técnica de búsqueda global más conocida y empleada. Este tipo de algoritmos presentan la capacidad de explorar y explotar espacios de búsqueda complejos, lo que les permite obtener soluciones muy próximas a la óptima. Además, la codificación genética que emplean les permite incorporar conocimiento a priori de una forma muy sencilla y aprovecharlo para guiar la búsqueda.En la presente tesis doctoral se proponen SDEs que tienen como objetivo principal el aprendizaje automático de particiones difusas para mejorar una técnica de modelado y simulación denominada Razonamiento Inductivo Difuso (FIR). Se persigue aprovechar las potencialidades de los AGs para aprender los parámetros de discretización de la metodología FIR, es decir, el número de clases por variable (granularidad) y las funciones de pertenencia (landmarks) que definen su semántica. Debido al hecho que es una metodología basada en lógica difusa, la eficiencia en el modelado y predicción de FIR está influenciada de forma directa por estos parámetros de discretización. Es así como, la determinación automática de parámetros adecuados de discretización en la metodología FIR surge como una alternativa de gran interés y utilidad al uso de valores heurísticos y/o por defecto. Más aún, automatizar la selección de los valores adecuados para estos parámetros permite el uso de la metodología FIR a usuarios no expertos en modelado de sistemas ni en lógica difusa garantizándoles el mejor rendimiento de esta metodología.Se presentan tres métodos evolutivos de aprendizaje automático de las particiones difusas: a) El aprendizaje de la granularidad con las funciones de pertenencia uniformes (AG1+EFP), b) El ajuste local de las funciones de pertenencia con un número fijo de clases para cada variable (AG1+AG2), y c) El aprendizaje en conjunto de la granularidad y de las funciones de pertenencia asociadas que definen su semántica (AG3). Dichos métodos han sido implementados en la herramienta de programación Matlab y sirven tanto para entornos Windows como para Linux.Los resultados obtenidos por los SDEs desarrollados han sido muy buenos en las cuatro aplicaciones estudiadas: sistema nervioso central humano, línea de media tensión en núcleos urbanos, estimación a corto plazo de concentraciones de ozono en Austria y estimación a largo plazo de concentraciones de ozono en México. Nuestros métodos evolutivos son los que presentan mayor eficiencia en el proceso de predicción si los comparamos con los obtenidos por otras metodologías en trabajos previos, por FIR usando valores por defecto y también, cosa no esperada, por FIR cuando los parámetros de fusificación han sido definidos por expertos en el área. En general, el AG3 y la combinación AG1+AG2, en ese orden, son los que han mostrado mejores resultados en todas las aplicaciones, seguidos por el AG1+EFP. Sin embargo el AG3 es el que presenta mayor costo computacional. Por lo tanto como conclusión general, debemos decir que los SDEs diseñados e implementados en esta tesis consiguen buenos resultados para la tarea que les ha sido encomendada en el entorno de la metodología FIR. Es pues el usuario quien debe decidir qué SDE resulta más conveniente para la aplicación que tiene entre manos, en función de las necesidades temporales y de precisión. / It is commonly established that more intelligent systems can be obtained by the hybridization of Soft Computing methodologies, in order that the weaknesses of some systems be compensated with the strengths of others. Neural Fuzzy Systems (NFSs) and Evolutionary Fuzzy Systems (EFSs) are the most notorious representatives of these hybrid systems.An Evolutionary Fuzzy System is basically a fuzzy system augmented by a learning process based on an evolutionary algorithm (EA), particularly Genetic Algorithms (GAs), which are currently considered as the most well-known employed global search technique. This kind of algorithms have the ability to explore and to exploit complex search spaces, which allows the obtaining of solutions very close to the optimal ones within these spaces. Besides, the genetic codification employed allows to incorporate a priori knowledge in a very simple way and to use it to guide the search.In this PhD. thesis, we propose EFSs that improves a modeling and simulation technique the Fuzzy Inductive Reasoning (FIR). The main goal of the EFSs is to take advantage of the potentialities of GAs to learn the fuzzification parameters of FIR, i.e. the number of classes per variable (granularity) and the membership functions (landmarks) that define its semantics. Due to the fact that it is a methodology based on fuzzy logic, FIR modeling and prediction performance is directly influenced by these discretization parameters. Therefore, the automatic determination of precise fuzzification parameters in the FIR methodology is an interesting and useful alternative to the use of heuristics and/or default values. Moreover, it is expected that the automatic selection of adequate values for these parameters will open up the FIR methodology to new users, with no experience neither in systems modeling nor in fuzzy logic, guaranteeing the best performance of this methodology.Three evolutionary methods of automatic learning of fuzzy partitions are presented: a) The learning of the granularity with uniform membership functions (GA1+EFP), b) The local tuning of the membership functions with a fixed number of classes per variable (GA1+GA2), and c) The learning at the same time of the granularity and the membership functions associated that define its semantics (GA3). The evolutionary methods have been implemented in Matlab and they run in both Windows and Linux environments.The results obtained by the EFSs developed in the four applications studied, i.e. human central nervous system, maintenance costs of electrical medium line in Spanish towns, short-term estimation of ozone concentration in Austria and long-term estimation of ozone concentration in Mexico, were very good. The results obtained by our evolutionary methods have presented higher efficiency in the prediction process than those obtained by other methodologies in previous works, by FIR using default values and, even, by FIR when the fuzzification parameters have been defined by experts in the area. In general, the GA3 and the combination GA1+GA2, in that order, are the ones that have shown better results in all the applications, followed by the GA1+EFP. However, GA3 is the algorithm that presents the greatest computational cost. As general conclusion, we must say that the EFSs designed and implemented in this thesis yielded good results for the task which they were entrusted in FIR methodology. Therefore, the user should decide what EFS turns out to be more convenient for the modeling application at hand in function of time and precision needs.
|
130 |
Conformance checking and diagnosis in process miningMunoz-Gama, Jorge 19 December 2014 (has links)
In the last decades, the capability of information systems to generate and record overwhelming amounts of event data has experimented an exponential growth in several domains, and in particular in industrial scenarios. Devices connected to the internet (internet of things), social interaction, mobile computing, and cloud computing provide new sources of event data and this trend will continue in the next decades. The omnipresence of large amounts of event data stored in logs is an important enabler for process mining, a novel discipline for addressing challenges related to business process management, process modeling, and business intelligence. Process mining techniques can be used to discover, analyze and improve real processes, by extracting models from observed behavior. The capability of these models to represent the reality determines the quality of the results obtained from them, conditioning its usefulness. Conformance checking is the aim of this thesis, where modeled and observed behavior are analyzed to determine if a model defines a faithful representation of the behavior observed a the log.
Most of the efforts in conformance checking have focused on measuring and ensuring that models capture all the behavior in the log, i.e., fitness. Other properties, such as ensuring a precise model (not including unnecessary behavior) have been disregarded. The first part of the thesis focuses on analyzing and measuring the precision dimension of conformance, where models describing precisely the reality are preferred to overly general models. The thesis includes a novel technique based on detecting escaping arcs, i.e., points where the modeled behavior deviates from the one reflected in log. The detected escaping arcs are used to determine, in terms of a metric, the precision between log and model, and to locate possible actuation points in order to achieve a more precise model. The thesis also presents a confidence interval on the provided precision metric, and a multi-factor measure to assess the severity of the detected imprecisions.
Checking conformance can be time consuming for real-life scenarios, and understanding the reasons behind the conformance mismatches can be an effort-demanding task. The second part of the thesis changes the focus from the precision dimension to the fitness dimension, and proposes the use of decomposed techniques in order to aid in checking and diagnosing fitness. The proposed approach is based on decomposing the model into single entry single exit components. The resulting fragments represent subprocesses within the main process with a simple interface with the rest of the model. Fitness checking per component provides well-localized conformance information, aiding on the diagnosis of the causes behind the problems. Moreover, the relations between components can be exploded to improve the diagnosis capabilities of the analysis, identifying areas with a high degree of mismatches, or providing a hierarchy for a zoom-in zoom-out analysis. Finally, the thesis proposed two main applications of the decomposed approach. First, the theory proposed is extended to incorporate data information for fitness checking in a decomposed manner. Second, a real-time event-based framework is presented for monitoring fitness. / En las últimas décadas, la capacidad de los sistemas de información para generar y almacenar datos de eventos ha experimentado un crecimiento exponencial, especialmente en contextos como el industrial. Dispositivos conectados permanentemente a Internet (Internet of things), redes sociales, teléfonos inteligentes, y la computación en la nube proporcionan nuevas fuentes de datos, una tendencia que continuará en los siguientes años. La omnipresencia de grandes volúmenes de datos de eventos almacenados en logs abre la puerta al Process Mining (Minería de Procesos), una nueva disciplina a caballo entre las técnicas de gestión de procesos de negocio, el modelado de procesos, y la inteligencia de negocio. Las técnicas de minería de procesos pueden usarse para descubrir, analizar, y mejorar procesos reales, a base de extraer modelos a partir del comportamiento observado. La capacidad de estos modelos para representar la realidad determina la calidad de los resultados que se obtengan, condicionando su efectividad. El Conformance Checking (Verificación de Conformidad), objetivo final de esta tesis, permite analizar los comportamientos observados y modelados, y determinar si el modelo es una fiel representación de la realidad. La mayoría de los esfuerzos en Conformance Checking se han centrado en medir y asegurar que los modelos fueran capaces de capturar todo el comportamiento observado, también llamado "fitness". Otras propiedades, tales como asegurar la "precisión" de los modelos (no modelar comportamiento innecesario) han sido relegados a un segundo plano. La primera parte de esta tesis se centra en analizar la precisión, donde modelos describiendo la realidad con precisión son preferidos a modelos demasiado genéricos. La tesis presenta una nueva técnica basada en detectar "arcos de escape", i.e. puntos donde el comportamiento modelado se desvía del comportamiento reflejado en el log. Estos arcos de escape son usados para determinar, en forma de métrica, el nivel de precisión entre un log y un modelo, y para localizar posibles puntos de mejora. La tesis también presenta un intervalo de confianza sobre la métrica, así como una métrica multi-factorial para medir la severidad de las imprecisiones detectadas. Conformance Checking puede ser una operación costosa para escenarios reales, y entender las razones que causan los problemas requiere esfuerzo. La segunda parte de la tesis cambia el foco (de precisión a fitness), y propone el uso de técnicas de descomposición para ayudar en la verificación de fitness. Las técnicas propuestas se basan en descomponer el modelo en componentes con una sola entrada y una sola salida, llamados SESEs. Estos componentes representan subprocesos dentro del proceso principal. Verificar el fitness a nivel de subproceso proporciona una información detallada de dónde están los problemas, ayudando en su diagnóstico. Además, las relaciones entre subprocesos pueden ser explotadas para mejorar las capacidades de diagnóstico e identificar qué áreas concentran la mayor densidad de problemas. Finalmente, la tesis propone dos aplicaciones directas de las técnicas de descomposición: 1) la teoría es extendida para incluir información de datos a la verificación de fitness, y 2) el uso de sistemas descompuestos en tiempo real para monitorizar fitness
|
Page generated in 0.0565 seconds