Дисертації з теми "Parallel sets"

Many people in widely varied fields are exposed to categorical data describing myriad observations. The breadth of applications in which categorical data are used means that many of the people tasked to apply these data have not been trained in data analysis. Visualization of data is often used to alleviate this problem since visualization can convey relevant information in a non-mathematical manner. However, visualizations are frequently static and the tools to create them are largely geared towards quantitative data. It is the purpose of this thesis to demonstrate a method which expands on the parallel coordinates method of visualization and uses a 'Google Maps' style of interaction and view dependent data presentation for visualizing and exploring categorical data that is accessible by non-experts and promotes the use of domain specific knowledge. The parallel coordinates method has enjoyed increasing popularity in recent times, but has several shortcomings. This thesis seeks to address some of these problems in a manner which involves not just addressing the final static image which is generated, but the paradigm of interaction as well.

Die Recurrence Quantification Analysis (RQA) ist eine Methode aus der nicht-linearen Zeitreihenanalyse. Im Mittelpunkt dieser Methode steht die Auswertung des Inhalts sogenannter Rekurrenzmatrizen. Bestehende Berechnungsansätze zur Durchführung der RQA können entweder nur Zeitreihen bis zu einer bestimmten Länge verarbeiten oder benötigen viel Zeit zur Analyse von sehr langen Zeitreihen. Diese Dissertation stellt die sogenannte skalierbare Rekurrenzanalyse (SRA) vor. Sie ist ein neuartiger Berechnungsansatz, der eine gegebene Rekurrenzmatrix in mehrere Submatrizen unterteilt. Jede Submatrix wird von einem Berechnungsgerät in massiv-paralleler Art und Weise untersucht. Dieser Ansatz wird unter Verwendung der OpenCL-Schnittstelle umgesetzt. Anhand mehrerer Experimente wird demonstriert, dass SRA massive Leistungssteigerungen im Vergleich zu existierenden Berechnungsansätzen insbesondere durch den Einsatz von Grafikkarten ermöglicht. Die Dissertation enthält eine ausführliche Evaluation, die den Einfluss der Anwendung mehrerer Datenbankkonzepte, wie z.B. die Repräsentation der Eingangsdaten, auf die RQA-Verarbeitungskette analysiert. Es wird untersucht, inwiefern unterschiedliche Ausprägungen dieser Konzepte Einfluss auf die Effizienz der Analyse auf verschiedenen Berechnungsgeräten haben. Abschließend wird ein automatischer Optimierungsansatz vorgestellt, der performante RQA-Implementierungen für ein gegebenes Analyseszenario in Kombination mit einer Hardware-Plattform dynamisch bestimmt. Neben anderen Aspekten werden drastische Effizienzgewinne durch den Einsatz des Optimierungsansatzes aufgezeigt.
Recurrence quantification analysis (RQA) is a method from nonlinear time series analysis. It relies on the identification of line structures within so-called recurrence matrices and comprises a set of scalar measures. Existing computing approaches to RQA are either not capable of processing recurrence matrices exceeding a certain size or suffer from long runtimes considering time series that contain hundreds of thousands of data points. This thesis introduces scalable recurrence analysis (SRA), which is an alternative computing approach that subdivides a recurrence matrix into multiple sub matrices. Each sub matrix is processed individually in a massively parallel manner by a single compute device. This is implemented exemplarily using the OpenCL framework. It is shown that this approach delivers considerable performance improvements in comparison to state-of-the-art RQA software by exploiting the computing capabilities of many-core hardware architectures, in particular graphics cards. The usage of OpenCL allows to execute identical SRA implementations on a variety of hardware platforms having different architectural properties. An extensive evaluation analyses the impact of applying concepts from database technology, such memory storage layouts, to the RQA processing pipeline. It is investigated how different realisations of these concepts affect the performance of the computations on different types of compute devices. Finally, an approach based on automatic performance tuning is introduced that automatically selects well-performing RQA implementations for a given analytical scenario on specific computing hardware. Among others, it is demonstrated that the customised auto-tuning approach allows to considerably increase the efficiency of the processing by adapting the implementation selection.

Orientador: Prof. Raphael Yokoingawa de Camargo
Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Neurociência e Cognição, 2014.
Nowadays, utilizing co-processors, accelerators and specially GPGPU computation are widely accepted as a new paradigm of High Performance Computing (HPC). However, developing softwares that can utilize available resources still remains a challenging task. In other side, scientist have used legacy CPU-based simulators for decades and many of them are still the main tools in different fields of science. In fact, any activity that can combine the legacy simulators with powerful co-processors devices is in the main interest. In this project, we design and develop a simulation engine, Parallel Neural Network Simulator (PN2S), to communicate with MOOSE simulator (A well-known tools by Neuroscientists) and provide CUDA based execution for simulating realistic neural network models. The simulation engine maps the voltage distribution in neuron¿s body to sets of linear systems and solve them on GPU. To provide usable functionality, we also developed solver for active channels which support Hodgkin-Huxley model of ionic channels. We compared the engine with CPU version for both homogeneous simple models and randomly generated heterogeneous network. The evaluation focused on performance and also covered the accuracy of the simulation. The experimental results, showed that by facilitating PN2S engine, we can significantly increase the performance of a simulation engine, since its execution is quite transparent to the users and major parts of the host simulator.

Data race in parallel programs can be difficult to precisely detect, and doing so manually can often prove unsuccessful. Task parallel programming models can help reduce defects introduced by the programmer by restricting concurrent functionalities to fork-join operations. Typical data race detection algorithms compute the happens-before relation either by tracking the order that shared accesses happen via a vector clock counter, or by grouping events into sets that help classify which heap locations are accessed sequentially or in parallel. Access sets are simple and efficient to compute, and have been shown to have the potential to outperform vector clock approaches in certain use cases. However, they do not support arbitrary thread synchronization, are limited to fork-join or similar structures, and do not support mutual exclusion. Vector clock approaches do not scale as well to many threads with many shared interactions, rendering them inefficient in many cases. This work combines the simplicity of access sets with the generality of vector clocks by grouping heap accesses into access sets, and attaching the vector clock counter to those groupings. By combining these two approaches, access sets can be utilized more generally to support programs that contain mutual exclusion. Additionally, entire blocks can be ordered with each other rather than single accesses, producing a much more efficient algorithm for data race detection. This novel algorithm, ZipperOTF, is compared to the Computation Graph algorithm (an access set algorithm) as well as FastTrack (a vector clock algorithm) to show comparisons in empirical results and in both time and space complexity.

The Fuzzy-ARTMAP (FAM) algorithm is one of the premier neural network architectures for classification problems. FAM can learn on line and is usually faster than other neural network approaches. Nevertheless the learning time of FAM can slow down considerably when the size of the training set increases into the hundreds of thousands. In this dissertation we apply data partitioning and network partitioning to the FAM algorithm in a sequential and parallel setting to achieve better convergence time and to efficiently train with large databases (hundreds of thousands of patterns). We implement our parallelization on a Beowulf clusters of workstations. This choice of platform requires that the process of parallelization be coarse grained. Extensive testing of all the approaches is done on three large datasets (half a million data points). One of them is the Forest Covertype database from Blackard and the other two are artificially generated Gaussian data with different percentages of overlap between classes. Speedups in the data partitioning approach reached the order of the hundreds without having to invest in parallel computation. Speedups on the network partitioning approach are close to linear on a cluster of workstations. Both methods allowed us to reduce the computation time of training the neural network in large databases from days to minutes. We prove formally that the workload balance of our network partitioning approaches will never be worse than an acceptable bound, and also demonstrate the correctness of these parallelization variants of FAM.
Ph.D.
School of Electrical and Computer Engineering
Engineering and Computer Science
Electrical and Computer Engineering

Дисертація на здобуття наукового ступеня доктора технічних наук зі спеціальності 05.01.01 – Прикладна геометрія, інженерна графіка. – Київський національний університет будівництва і архітектури, Київ, 2007. Дисертацію присвячено розробці теорії геометричного моделювання узагальнених паралельних множин для розв'язання задач формоутворення в часі геометричних об'єктів – наочних геометричних моделей динамічних явищ і процесів, що характеризуються хвильовими фронтами, поверхні яких у певні моменти часу утворюють просторову конформну сітку з лініями у напрямках руху цих фронтів, або характеризуються ізолініями, конформними до напрямків зміни фізичних параметрів. На основі введеної термінології запропоновано загальний підхід до геометричного моделювання проявів процесів і явищ різної фізичної природи. Розроблено теоретичні основи методу опису геометричних моделей паралельних множин на площині за допомогою рівнянь Гамільтона – Якобі у вигляді рівняння ейконала для кривих, що мають точки звороту або самі себе перетинають; методу опису геометричних моделей паралельних множин за допомогою нормальних рівнянь для поверхонь, які задано у параметричному вигляді; методу на основі конформних відображень, в якому запропоновано новий геометричний зміст функції комплексного потенціалу вихору і одержано нові геометричні моделі сімей квазіпаралельних ліній на комплексній площині. Удосконалено метод іміджевої екстраполяції для прогнозування геометричної форми ліній на площині, як елементів узагальнених паралельних множин. Розроблені методи дозволяють вивчати якісні зміни об'єктів, що моделюються.
Thesis for a doctor's degree in engineering sciences. Specialty: 05.01.01 – Applied geometry, engineering graphics. – Kyiv National University of Building and Architecture. – Kyiv, 2007. The dissertation is devoted to developing of the geometrical modelling theory of the general parallel sets for problems solving of geometrical objects form-formation in time which are visual geometrical models of dynamic phenomena and processes characterized by wave fronts surfaces which create the space conformal set in the moments of time with the lines on directions of these fronts moving or by isolines which are conformal to directions of physical parameters change. On introduced terminology basis the general approach to the geometrical modelling of different origin physical phenomena and processes displays is proposed. It was developed the theoretical basis of: the method of parallel sets geometrical models creation on the plane by means of Hamilton – Jacobi equation as eikonal equation for the curves with return and self-intersection points; the method of parallel sets geometrical models creation by means of normal equations for the surfaces in parameter form; the method based on conformal representations, in which the new geometrical meaning of twister complex potential function was proposed and the new geometrical models of quasi-parallel lines sets were obtained on the complex plane; the improved image extrapolation method for forecasting of geometrical form of lines on the plane as the elements of general parallel sets. These methods allow to research qualitative change of objects modelled.

Stateless model checking is a technique for testing and verifying concurrent programs, based on exploring the different ways in which operations executed by the processes of a concurrent program can be scheduled. The goal of the technique is to expose all behaviours that can be a result of scheduling non-determinism. As the number of possible schedulings is huge, however, techniques that reduce the number of schedulings that must be explored to achieve verification have been developed. Dynamic partial order reduction (DPOR) is a prominent such technique. This dissertation presents a number of improvements to dynamic partial order reduction that significantly increase the effectiveness of stateless model checking. Central among these improvements are the Source and Optimal DPOR algorithms (and the theoretical framework behind them) and a technique that allows the observability of the interference of operations to be used in dynamic partial order reduction. Each of these techniques can exponentially decrease the number of schedulings that need to be explored to verify a concurrent program. The dissertation also presents a simple bounding technique that is compatible with DPOR algorithms and effective for finding bugs in concurrent programs, if the number of schedulings is too big to make full verification possible in a reasonable amount of time, even when the improved algorithms are used. All improvements have been implemented in Concuerror, a tool for applying stateless model checking to Erlang programs. In order to increase the effectiveness of the tool, the interference of the high-level operations of the Erlang/OTP implementation is examined, classified and precisely characterized. Aspects of the implementation of the tool are also described. Finally, a use case is presented, showing how Concuerror was used to find bugs and verify key correctness properties in repair techniques for the CORFU chain replication protocol.
UPMARC
RELEASE

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-05T12:22:31Z No. of bitstreams: 1 lucianatoquinidelimasilva.pdf: 1503407 bytes, checksum: f19f0499ae2bed7fe2d0aba5da08adaf (MD5)
Rejected by Adriana Oliveira (adriana.oliveira@ufjf.edu.br), reason: on 2016-02-05T12:25:38Z (GMT)
Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-05T12:27:35Z No. of bitstreams: 1 lucianatoquinidelimasilva.pdf: 1503407 bytes, checksum: f19f0499ae2bed7fe2d0aba5da08adaf (MD5)
Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-05T15:22:21Z (GMT) No. of bitstreams: 1 lucianatoquinidelimasilva.pdf: 1503407 bytes, checksum: f19f0499ae2bed7fe2d0aba5da08adaf (MD5)
Made available in DSpace on 2016-02-05T15:22:21Z (GMT). No. of bitstreams: 1 lucianatoquinidelimasilva.pdf: 1503407 bytes, checksum: f19f0499ae2bed7fe2d0aba5da08adaf (MD5) Previous issue date: 2014-08-22
O presente trabalho tem como objetivo analisar a implementação do Programa de Recuperação Paralela, entre os anos de 2009 e 2012, em duas escolas rurais deEnsino Fundamental I, sendo vinculada uma à outra, situadas na cidade de Limeira, estado de São Paulo. A finalidade desse programa é recuperar a defasagem de aprendizagem dos alunos, evitando tanto a promoção automática sem a efetiva aquisição dos conhecimentos desejáveis a cada ano de escolaridade, quanto à reprovação no final dos ciclos, constituindo-se em uma estratégia importante para superar os desafios educacionais relacionados ao fracasso escolar.Para tanto, fez-se necessário verificar a ação dos atores envolvidos na prática, identificar quais os fatores relacionados à gestão se configuram como entraves ao Programa no que se relaciona à legítima qualidade da recuperação da aprendizagem dos alunos, além de investigar os efeitos sobre o seu desempenho. A intenção, a partir das informações investigadas, foi elaborar uma proposta de intervenção para aperfeiçoamento e monitoramento do Programa nas respectivas unidades escolares, visando à melhoria do processo de recuperação de aprendizagem, visto que os resultados das avaliações externas apresentaram declínio das médias nos anos pesquisados. O referencial metodológico para a coleta de dados pautou-se na abordagem qualitativa e quantitativa, sendo utilizados documentos oficiais normatizadores e reguladores referentes ao Programa de Recuperação Paralela, assim como registros intraescolares. Como instrumentos de pesquisa foram utilizados questionários com os professores da classe regular e entrevistas semiestruturadas com o professor da classe de recuperação paralela, professor coordenador pedagógico e vice-diretor. O embasamento teórico desta pesquisa tem como autores principais Heloísa Luck eThelma Polon, que abordam a temática das ações gestoras relacionadas ao monitoramento do desempenho dos alunos, Danilo Gandin eAraujo, que retratam a importância do planejamento participativo, visando ao trabalho colaborativo. Ainda, foram utilizados os estudos de Isabel Alarcão eJosé Carlos Libâneo naquilo que se relaciona à formação continuada inserida no contexto escolar. O resultado da pesquisa demonstrou que as ações dos atores envolvidos, especialmente do gestor escolar, denunciam a falta de planejamento organizado de forma participativa, sobre a perspectiva da cultura colaborativae a ausência de efetivo monitoramento do desempenho discente e de ações de formação continuada dentro do contexto escolar, o que requer desenvolvimento de ações que revertam a situação identificada e possibilitem maior eficiência e eficácia do Programa de Recuperação Paralela.
The present study aims to analyze the implementation of the Recovery Program Parallel, between the years 2009 and 2012 in two rural elementary schools Teaching I, being linked to each other, located in the city of Limeira, São Paulo state. The purpose of this program is to recover the gap of student learning, avoiding both the automatic promotion without the effective acquisition of desirable each year of schooling knowledge, as to fail at the end of cycles, thus becoming an important strategy to overcome the challenges education related to school failure. To this end, it was necessary to check the action of the actors involved in the practice, identify the factors related to management are configured as barriers to program, as it relates to the lawful recovery of quality of student performance, and to investigate the effects on performance . The intention, from the information investigated, was to draft a proposal for intervention for improvement and monitoring program in their school units in order to improve the recovery of the learning process, since the results of external evaluations show a decline in the years surveyed. The methodological framework for data collection was based on qualitative and quantitative approach, standard-setters and regulators official documents relating to Parallel Recovery Program, as well as intra school records being used. The research tools used questionnaires to teachers of regular classes and semi-structured interviews with the teacher of the class of parallel recovery, teacher pedagogical coordinator and deputy director were used. The theoretical basis of this study's main authors Heloise Luck and Thelma Polon, addressing the theme of management actions related to monitoring of student performance, and DaniloGandin Araujo that depict the importance of participatory planning, aiming to collaborative work. Still, studies Alarcão Isabel and Jose Carlos Libâneo in what relates to the inserted continuing education in the school context were used. The research result showed that the actions of the actors involved, especially the school manager, points to the lack of organized planning in a participatory way, from the perspective of collaborative culture and the absence of effective monitoring of student performance and actions of continuing education within the context school, which requires development of actions to reverse the situation identified and could improve the efficiency and effectiveness of the Recovery Program Parallel.

Made available in DSpace on 2013-08-07T18:43:12Z (GMT). No. of bitstreams: 1 000440021-Texto+Completo-0.pdf: 859301 bytes, checksum: 74c835c02a03141cc25fe26c323fab1d (MD5) Previous issue date: 2012
Transactional Memory is considered by many researchers to be one of the most promising solutions to address the problem of programming multicore processors. This model provides the scalability of fine-grained locking while avoiding common issues of tradicional mechanisms, such as deadlocks. During these almost twenty years of research, several studies were carried out to identify approaches in order to maximize the use of Transactional Memories in the Parallel Programming scenario. Furthermore, several TM systems have been developed in different types of implementations as well as new Benchmarks were proposed for evaluation and testing of TM systems. However, despite advances in the area, Transactional Memory is not considered yet a ready solution by the scientific community, due to unanswered questions in the literature, such as: “How to identify if an application has an advantage using Transactional Memory?” and “Why some applications do not benefit from the use of Transactional Memories?”, This work presents a comparative evaluation of a set of transactional applications and systems, introducing the field current state-of-the-art, understanding the existing problems and identifying growth opportunities in the STM systems in order to contribute to answer the questions that remain open in the scientific community.
Memórias Transacionais são consideradas por muitos pesquisadores como a mais promissora solução para resolver problemas de programação multicore. Esse modelo promete escalabilidade com pequena granularidade, enquanto elimina os problemas comuns nos mecanismos convencionais de locks, como deadlocks por exemplo. Durante esses quase vinte anos de pesquisas, diversos estudos foram realizados visando identificar abordagens para maximizar o uso de Memórias Transacionais no cenário de Programação Paralela. Além disso, diversos sistemas TM foram desenvolvidos em diferentes tipos de implementações, bem como novos Benchmarks foram propostos para avaliação e testes de sistemas TM. Entretanto, apesar do avanço da área, Memória Transacional não é considerada uma solução pronta para comunidade científica devido às perguntas ainda não respondidas na literatura, tais como: “Como identificar se uma aplicação terá vantagem na utilização de memórias transacionais?” e “Porque algumas aplicações não se beneficiam com o uso de Memórias Transacionais?”. Esse trabalho realiza uma avaliação comparativa de um conjunto de sistemas e aplicações transacionais, apresentando o estado da arte atual, compreendendo os problemas existentes e identificando oportunidades de crescimento nos sistemas STM de maneira a contribuir para responder as perguntas ainda em aberto na comunidade científica.

Made available in DSpace on 2015-04-14T14:49:52Z (GMT). No. of bitstreams: 1 440021.pdf: 859301 bytes, checksum: 74c835c02a03141cc25fe26c323fab1d (MD5) Previous issue date: 2012-03-29
Transactional Memory is considered by many researchers to be one of the most promising solutions to address the problem of programming multicore processors. This model provides the scalability of fine-grained locking while avoiding common issues of tradicional mechanisms, such as deadlocks. During these almost twenty years of research, several studies were carried out to identify approaches in order to maximize the use of Transactional Memories in the Parallel Programming scenario. Furthermore, several TM systems have been developed in different types of implementations as well as new Benchmarks were proposed for evaluation and testing of TM systems. However, despite advances in the area, Transactional Memory is not considered yet a ready solution by the scientific community, due to unanswered questions in the literature, such as: How to identify if an application has an advantage using Transactional Memory? and Why some applications do not benefit from the use of Transactional Memories? , This work presents a comparative evaluation of a set of transactional applications and systems, introducing the field current state-of-the-art, understanding the existing problems and identifying growth opportunities in the STM systems in order to contribute to answer the questions that remain open in the scientific community.
Mem?rias Transacionais s?o consideradas por muitos pesquisadores como a mais promissora solu??o para resolver problemas de programa??o multicore. Esse modelo promete escalabilidade com pequena granularidade, enquanto elimina os problemas comuns nos mecanismos convencionais de locks, como deadlocks por exemplo. Durante esses quase vinte anos de pesquisas, diversos estudos foram realizados visando identificar abordagens para maximizar o uso de Mem?rias Transacionais no cen?rio de Programa??o Paralela. Al?m disso, diversos sistemas TM foram desenvolvidos em diferentes tipos de implementa??es, bem como novos Benchmarks foram propostos para avalia??o e testes de sistemas TM. Entretanto, apesar do avan?o da ?rea, Mem?ria Transacional n?o ? considerada uma solu??o pronta para comunidade cient?fica devido ?s perguntas ainda n?o respondidas na literatura, tais como: Como identificar se uma aplica??o ter? vantagem na utiliza??o de mem?rias transacionais? e Porque algumas aplica??es n?o se beneficiam com o uso de Mem?rias Transacionais?. Esse trabalho realiza uma avalia??o comparativa de um conjunto de sistemas e aplica??es transacionais, apresentando o estado da arte atual, compreendendo os problemas existentes e identificando oportunidades de crescimento nos sistemas STM de maneira a contribuir para responder as perguntas ainda em aberto na comunidade cient?fica.

As empresas estão utilizando diversos processos de melhoria para adequarem seus negócios às necessidades dos clientes, à maior concorrência, a uma necessidade de flexibilização e de redução dos custos de seus processos de manufatura. O seis sigma e a produção enxuta são dois processos utilizados por empresas no Brasile no mundo. Atualmente a integração destes processos é um desafio para essas empresas, que buscam uma maneira mais eficiente de reduzir seus desperdícios e se adaptarem às necessidades de seus mercados consumidores. Surge, assim, o Lean Sigma aplicado nas empresas de diversas formas. O objetivo deste trabalho é estruturar, por meio de dois estudos de caso, como as empresas estão utilizando o seis Sigma e a Produção Enxuta em seus processos de melhoria. Verificou-se que existem diferentes formas de utilizar os processos em paralelo: na primeira empresa o processo iniciou em conjunto e depois foi separado em dois processos paralelos de melhoria. A segunda empresa foi ao contrário, começando de forma paralela, desagregada, e posteriormente se unindo em um único processo de melhoria, denominado Lean Sigma. O trabalho apresenta uma sistematização do processo de melhoria de duas empresas, dividido em Visão Geral e Objetivos, Estrutura Organizacional e Métodos de Melhoria. Foram verificadas as formas gerais de utilização dos processos de melhoria e que uma abordagem integrada, que contemple as peculiaridades de cada processo, se demonstra como uma melhor opção para um processo de melhoria que utiliza a Produção Enxuta e o Seis Sigma paralelamente. A pesquisa traz, também, como resultado, uma proposta de sistematização do Lean Sigma, considerando o conhecimento adquirido nos estudos de caso e na literatura consultada.
Enterprises are using several improvement processes to adequate their business to the clients needs, to the higher competition, to a need of been more flexible and to reduce the costs of their manufacturing costs. The Six Sigma and the Lean Production are two processes using by enterprises in Brazil and the world wide. Nowadays the integration of those two processes is a challenge to enterprises that search a more efficient way to reduce their wastes and get adapted to the needs of their markets. With this objective the Lean Sigma appears, been applied in the enterprises differently. The dissertation objective is to understand, trough two case studies, how enterprises are connecting Six Sigma and Lean Production in their improvement processes. It was verified that are several ways to run the processes in parallel: in the first enterprise, the two processes was integrated and them shared into two process in parallel. The second enterprise showed the opposite approach, beginning disintegrated, in parallel, and them running together in one improvement processes, called Lean Sigma. The dissertation presents the systematization of the improvement processes of these two enterprises, organized as follow: Global vision and Objectives, Organizational Structure and Improvement Method. Was verified the general approach used in the improvement process and that the integrated approach, that consider the peculiarities of each process, showns as a best option to run Lean Production and Six Sigma in parallel. The research presents, as a result too, a systematization proposal for Lean Sigma, considering the case studies and the consulted literature.

El presente trabajo muestra el diseño de un mecanismo paralelo del tipo plataforma de seis grados de libertad y apoyos móviles que puede ser utilizado en un simulador de automóviles para el entrenamiento de conductores en nuestro país. El objetivo está centrado en lograr el diseño mecánico dejando pase a futuras investigaciones como el análisis de simulación mecánica, el diseño del sistema de control del mismo, entre otros que puedan complementar y optimizar el diseño de un simulador de manejo automatizado. A diferencia de muchos mecanismos utilizados para esta aplicación (tales como las plataformas Stewart Gough), este sistema no cuenta con actuadores de longitud variable, sino con barras de longitud constante cuyos apoyos en la base deslizan sobre rieles circulares. Para poder desarrollar este trabajo, se realizó una revisión de los fundamentos teóricos y el estado de la tecnología de los mecanismos en general, los robots paralelos y su aplicación hacia los simuladores de manejo. También se utilizaron investigaciones anteriores que analizaron el espacio de trabajo de este tipo de plataformas de barras que deslizan sobre un riel circular. Esta información fue de vital importancia para lograr el diseño conceptual pues brindó los requerimientos de movimiento que los simuladores de manejo poseen. A partir de ello se pudieron diseñar cada uno de los componentes del sistema de modo que puedan resistir los movimientos y cargas de la plataforma considerando sobre ella una carga de hasta 250 kg, la cual representa la masa de una persona y la de una estructura o cabina en donde ella pueda ubicarse. Este tipo de mecanismo es una buena alternativa para los simuladores porque logran incrementar el espacio de trabajo hasta 1,6 veces respecto a las plataformas convencionales como la Stewart Gough; además, su movimiento giratorio es menos restringido. Por otro lado, la utilización de un simulador para entrenamiento de conductores en nuestro país sería una buena alternativa frente a los peligros e inseguridad que enfrentan quienes conducen por primera vez, sobre todo en nuestra capital.
Tesis

碩士
國立中山大學
電機工程研究所
85
It is an important issue to generate local memory access sequences and communication sets efficiently in compiling a data@parallel language into a SPMD (Single Program Multiple Data) code. Recently, several approaches based on the case that arrays are distributed using block-cyclic distribution with arbitrary block sizes across arbitrary number of processors have been presented. Typically, in order to generate explicit communication sets, each node program has to scan over the local memory access sequences. In this thesis, we focus on two cases. First, arrays are aligned to a common template and this template is distributed using block-cyclic distribution across processors. Second, arrays are distributed using block-cyclic distribution with the same block size across the same number of processors. The first case is classified into one-level and two-level mappings. Under these conditions, we present a scheme to efficiently generate communication sets. We use a class table to store the information from the array regular section and data distribution. Given the regular sections and data distributions, we can utilize the class tables to generate the block pattern tables storing the information within a block that the sets of active elements referenced to the same block. Furthermore, we construct a block statp graph to generate communication sets by scanning only a portion of local memory access sequences. Without considering the lower bound and the upper bound blocks in the layout of regular section, for one-level mappings and the second case, we only need to scan the first s local blocks; for two-level mappings, only need to scan the first α*s local blocks, where s is the stride of regular section and α is the stride of alignment function. The experimental results do confirm the advantage of our scheme, especially when the stride of regular section is smaller than the block size. As the result, the efficiency can be greatly improved.

博士
國立中央大學
資訊工程研究所
86
This dissertation addresses the issues of generating computation andcommunication sets for data-parallel programs on distributed-memorymulticomputers. Data-parallel programs provide a global address space and data distribution directives for programmers to specify data distribution.A parallelizing compiler for data-parallel languages should distributecomputation onto processors by the owner-computes rule, allocate data across processors by user-specified data distribution directives, and managecommunication among processors for non-local data elements. In general, data- parallel languages use a two-level mapping for data to processor mapping.A two-level mapping provides user to specify the data- processor mapping byaligning related array objects with a template, and then distributing the template onto the user- declared abstract processors. Three regular data distributions, block, cyclic, and block-cyclic data distributions, are provided by data-parallel languages. The most general data distribution among the three distributions is the block-cyclic distribution. Hence, the dissertation proposes several compilation techniques to deal with the computation and communication sets generations for two-level mappings withblock-cyclic distribution. First of all, we present a scheme to efficiently generate the computation and communication sets for one-level mappings. A one-level mapping is a special case of a two-level mapping, which assumes that the array elements are identically aligned with the template. We use a class table to store the information that is extracted from the array statements and data distribution patterns. Given data distributions and an array statement, we can use theclass table to generate the communication sets in closed forms. Furthermore, we derive the SPMD codes for sending and receiving the necessary data between processors. An algorithm to generate the class table is presented. The time complexity of this algorithm is O(s), where s is the array access stride.The technique to generate communication sets for single induction variablehas been implemented on a DEC Alpha 3000 workstation. The experimental results do confirm the advantages of our scheme, especially when the array access stride is larger than the distribution block size. We also extend our approach to a perfectly n-nested loop with general affine subscripts. The time complexity to construct all different class tables is O(s^2). In this dissertation, we also propose compilation techniques to compressholes, which are caused by the non-unit alignment stride in a two-leveldata- processor mapping. Holes are the memory locations mapped by useless template cells. To fully utilize the memory space, memory holes should be removed. In a two-level data-processor mapping, there is a repetitive pattern for array elements mapped onto processors. We classify blocks into classes and use a class table to record the distribution of each class in the first repetitive data distribution pattern. Similarly, data distribution on a processor also has a repetitive pattern. We use a compression table to record the distribution of each block in the first repetitive data distribution pattern on a processor. By using class table and compression table, hole compression can be easily and efficiently achieved. Compressing holes can save memory usage, improve spatial locality and further increase system performance.The proposed method is efficient, stable and easy implement. The experimental results do confirm the advantages of our proposed method over existing methods.Moreover, based on the premise of hole compression, the computation andcommunication sets generations for an array statement and data redistributionare presented as well. A more efficient compilation technique to generate the computation sets forblock-cyclically distributed array references with affine subscripts in atwo-nested loop is also proposed in this dissertation. For the memory accesses of an array reference with affine subscript within a two-nested loop, there exist repetitive patterns both at the outer and the inner loops. We use tables to record the memory accesses of repetitive patterns. According to these tables, a new start-computation algorithm is proposed to compute the starting elements on a processor for each outer loop iteration. The complexities of the table constructions are O(k+s2), where k is the distribution block size and s2 is the access stride for the inner loop. After tables are constructed, generating each starting element for each outer loop iteration can run in O(1) time. Moreover, we also show that the repetitive iterations for the outer loop are Pk/gcd(Pk, s1), where P is the number of processors and s1 is the access stride for the outer loop. Therefore, the total complexity to generate the computation sets for a block- cyclically distributed array with affine subscript in a two- nested loop is O(Pk/gcd(Pk, s1)+k+s2). The proposed approach is betterthan the known methods if s2 < Pk^2. In general, s2 is much smaller than Pk in real applications. Thus, the dominated term would be Pk. As a result, our proposed approach is much better than the existing methods. Moreover, the techniques proposed in the dissertation have been implementedand incorporated into our long-term project named UPPER (User- interactiveParallel Programming EnviRonment). This environment is designed and implementedat a DEC Alpha 3000 workstation with Motif environment. Given a data-parallel program (HPF, in this environment), we can generate the computation and communication sets as well as the SPMD code. The parallel execution platform is nCUBE/2. The generated SPMD code can be run on nCUBE/2 with user-specified number of processors. The performance analyses and comparisons are also given.

Monitoring and debugging distributed systems is inherently a difficult problem. Events collected during the execution of distributed systems can enable developers to diagnose and fix faults. Process-time diagrams are normally used to view the relationships between the events and understand the interaction between processes over time. A major difficulty with analyzing these sets of events is that they are usually very large. Therefore, being able to search through the event-data sets can enable users to get to points of interest quickly and find out if patterns in the dataset represent the expected behaviour of the system. A lot of research work has been done to improve the search algorithm for finding event-patterns in large partial-order datasets. In this thesis, we improve on this work by parallelizing the search algorithm. This is useful as many computers these days have more than one core or processor. Therefore, it makes sense to exploit this available computing power as part of an effort to improve the speed of the algorithm. The search problem itself can be modeled as a Constraint Satisfaction Problem (CSP). We develop a simple and efficient way of generating tasks (to be executed by the cores) that guarantees that no two cores will ever repeat the same work-effort during the search. Our approach is generic and can be applied to any CSP consisting of a large domain space. We also implement an efficient dynamic work-stealing strategy that ensures the cores are kept busy throughout the execution of the parallel algorithm. We evaluate the efficiency and scalability of our algorithm through experiments and show that we can achieve efficiencies of up to 80% on a 24-core machine.

This thesis focuses on the engineering of algorithms for massive data sets. In recent years, massive data sets have become ubiquitous and existing computing applications, for the most part, cannot handle these data sets efficiently: either they crash or their performance degrades to a point where they take unacceptably long to process the input. Parallel computing and I/O-efficient algorithms provide the means to process massive amounts of data efficiently. The work presented in this thesis makes use of these techniques and focuses on obtaining practically efficient solutions for specific problems in computational geometry and graph theory. We focus our attention first on skyline computations. This problem arises in decision-making applications and has been well studied in computational geometry and also by the database community in recent years. Most of the previous work on this problem has focused on sequential computations using a single processor, and the algorithms produced are not able to efficiently process data sets beyond the capacity of main memory. Such massive data sets are becoming more common; thus, parallelizing the skyline computation and eliminating the I/O bottleneck in large-scale computations is increasingly important in order to retrieve the results in a reasonable amount of time. Furthermore, we address two fundamental problems of graph analysis that appear in many application areas and which have eluded efforts to develop theoretically I/O-efficient solutions: computing the strongly connected components of a directed graph and topological sorting of a directed acyclic graph. To approach these problems, we designed algorithms, developed efficient implementations and, using extensive experiments, verified that they perform well in practice. Our solutions are based on well understood algorithmic techniques. The experiments show that, even though some of these techniques do not lead to provably efficient algorithms, they do lead to practically efficient heuristic solutions. In particular, our parallel algorithm for skyline computation is based on divide-and-conquer, while the strong connectivity and topological sorting algorithms use techniques such as graph contraction, the Euler technique, list ranking, and time-forward processing.

We introduce a multiple subpopulation approach for parallel evolutionary algorithms the migration scheme of which follows a SOM-like dynamics. We succesfully apply this approach to clustering in both VLSI-design and psychotherapy research. The advantages of the approach are shown which consist in a reduced communication overhead between the sub-populations preserving a non-vanishing information flow.

Indiana University-Purdue University Indianapolis (IUPUI)
In the forensic science community, there is a vast need for tools to help assist investigations when standard DNA profiling methods are uninformative. Methods such as Forensic DNA Phenotyping (FDP) and proteomics aims to help this problem and provide aid in investigations when other methods have been exhausted. FDP is useful by providing physical appearance information, while proteomics allows for the examination of difficult samples, such as hair, to infer human identity and ancestry. To create a “biological eye witness” or develop informative probability of identity match statistics through proteomically inferred genetic profiles, it is necessary to constantly strive to improve these methods. Currently, two developmentally validated FDP prediction assays, ‘HIrisPlex’ and ‘HIrisplex-S’, are used on the capillary electrophoresis to develop a phenotypic prediction for eye, hair, and skin color based on 41 variants. Although highly useful, these assays are limited in their ability when used on the CE due to a 25 variant per assay cap. To overcome these limitations and expand the capacities of FDP, we successfully designed and validated a massive parallel sequencing (MPS) assay for use on both the ThermoFisher Scientific Ion Torrent and Illumina MiSeq systems that incorporates all HIrisPlex-S variants into one sensitive assay. With the migration of this assay to an MPS platform, we were able to create a semi-automated pipeline to extract SNP-specific sequencing data that can then be easily uploaded to the freely accessible online phenotypic prediction tool (found at https://hirisplex.erasmusmc.nl) and a mixture deconvolution tool with built-in read count thresholds. Based on sequencing reads counts, this tool can be used to assist in the separation of difficult two-person mixture samples and outline the confidence in each genotype call. In addition to FDP, proteomic methods, specifically in hair protein analysis, opens doors and possibilities for forensic investigations when standard DNA profiling methods come up short. Here, we analyzed 233 genetically variant peptides (GVPs) within hair-associated proteins and genes for 66 individuals. We assessed the proteomic methods ability to accurately infer and detect genotypes at each of the 233 SNPs and generated statistics for the probability of identity (PID). Of these markers, 32 passed all quality control and population genetics criteria and displayed an average PID of 3.58 x 10-4. A population genetics assessment was also conducted to identify any SNP that could be used to infer ancestry and/or identity. Providing this information is valuable for the future use of this set of markers for human identification in forensic science settings.

博士
國立中山大學
電機工程學系研究所
91
Distributed-memory multiprocessors offer very high levels of performance that are required to solve scientific applications. A traditional programming language cannot be expected to yield good performance when used to program such machines. Data-parallel languages provide programmers with a global memory and relieve them from the burden of inserting time-consuming, error-prone inter-processor communication. The compilers of these languages perform this task. Data-parallel languages also enable the programmers to establish alignment and distribution directives which specify the type of data parallelism and data mapping to the underlying parallel architecture. Parallelizing compilers distribute data and generate code according to the owner-computes rule when compiling an array statement. The array elements in a processor it owns are only a fraction of all the array elements. Not all of the array elements in the processor are active elements, so determining local memory access sequence is important. However, generating local memory access sequences becomes rather complicated when the array references involve complex subscripts. This study considers two types of complex subscript ― coupled subscripts and multiple induction variables. A processor may refer to the rhs (right-hand side) array elements owned by other processors, and the movement of data is inevitable. The overhead to access non-local data by inter-processor communication may be around 10 to 100 times more than the cost of accessing local data. Efficiently generating communication sets is important. This thesis introduces the concept of block compression/decompression, using smaller iteration tables, course distance and local block distance to solve problems of local memory access sequences, coupled scripts, MIV subscripts and communication set generation. Related work on these problems is reviewed and experimental results to demonstrate the benefit of the proposed methods.

碩士
國立交通大學
運輸與物流管理學系
106
Rail has been one of the most important transportation modes in Taiwan. With the progress of technology, the railway industry has gradually improved the speed and the service quality. However, it appears that not many studies have been from the aspect of management, especially the revenue management (RM) techniques used in this research. In this study, in order to increase the revenue, ticket sales are controlled by setting up booking limits. In particular, the parallel-train feature and the unreserved (free) seats are taken into consideration. This is because for railway operation, multiple trains may depart within in a short period of time. Therefore, customers may consider all suitable trains, the so-called parallel trains, when making their decision. In addition to the consideration over parallel trains, another very important characteristic of railway transportation is the case of unreserved seats, in which passengers are accepted without having a fixed seat assignment. In terms of model formulation, this study develop an integer programming (IP) model, which determines the booking limits of each train for each origin-destination. In order to evaluate the increase of revenue contributed by the IP model, a simulation experiment has been performed, by simulating the ticket purchase behavior of the customers, under the booking control based on the booking limits derived by the mathematical programming model and different control policies. In the numerical experiment, the revenues for different control policies under various conditions are analyzed. Based on the experiment results, it can be found that the booking control based on the model developed in this study can lead to higher revenue than the simply first-come-first-served (FCFS) control, and the gap between them is in general about 3%.

yes
This Workshop on Membrane Computing, at the Conference of Unconventional Computation and Natural Computation (UCNC), 12th July 2016, Manchester, UK, is the second event of this type after the Workshop at UCNC 2015 in Auckland, New Zealand*. Following the tradition of the 2015 Workshop the Proceedings are published as technical report. The Workshop consisted of one invited talk and six contributed presentations (three full papers and three extended abstracts) covering a broad spectrum of topics in Membrane Computing, from computational and complexity theory to formal verification, simulation and applications in robotics. All these papers – see below, but the last extended abstract, are included in this volume. The invited talk given by Rudolf Freund, “P SystemsWorking in Set Modes”, presented a general overview on basic topics in the theory of Membrane Computing as well as new developments and future research directions in this area. Radu Nicolescu in “Distributed and Parallel Dynamic Programming Algorithms Modelled on cP Systems” presented an interesting dynamic programming algorithm in a distributed and parallel setting based on P systems enriched with adequate data structure and programming concepts representation. Omar Belingheri, Antonio E. Porreca and Claudio Zandron showed in “P Systems with Hybrid Sets” that P systems with negative multiplicities of objects are less powerful than Turing machines. Artiom Alhazov, Rudolf Freund and Sergiu Ivanov presented in “Extended Spiking Neural P Systems with States” new results regading the newly introduced topic of spiking neural P systems where states are considered. “Selection Criteria for Statistical Model Checker”, by Mehmet E. Bakir and Mike Stannett, presented some early experiments in selecting adequate statistical model checkers for biological systems modelled with P systems. In “Towards Agent-Based Simulation of Kernel P Systems using FLAME and FLAME GPU”, Raluca Lefticaru, Luis F. Macías-Ramos, Ionuţ M. Niculescu, Laurenţiu Mierlă presented some of the advatages of implementing kernel P systems simulations in FLAME. Andrei G. Florea and Cătălin Buiu, in “An Efficient Implementation and Integration of a P Colony Simulator for Swarm Robotics Applications" presented an interesting and efficient implementation based on P colonies for swarms of Kilobot robots. *http://ucnc15.wordpress.fos.auckland.ac.nz/workshop-on-membrane-computingwmc- at-the-conference-on-unconventional-computation-natural-computation/