Spelling suggestions: "subject:"distribuido"" "subject:"distribuidos""
141 |
Diseño de un sistema distribuido de antenas para la optimización de cobertura en la estación central del metropolitanoGutiérrez Salinas, Xavier André, Rivera Cardenas, Juan Gabriel January 2015 (has links)
La presente tesis consiste en el diseño de un sistema MIMO mediante la tecnología DAS (Distributed Antenna System), orientada a una red RF Indoor en la estación central del metropolitano, mejorando la cobertura de señal de los sistemas 2G, 3G y 4G.
La tesis se ha organizado de la siguiente forma:
En el primer capítulo se presenta el planteamiento del estudio de investigación, identificando las problemáticas existentes, trazando objetivos a lograr al final de la tesis. Parte importante de este capítulo es la justificación del estudio y su importancia que posee, así también identificar las variables, para finalmente tener un claro concepto de la problemática.
En el segundo capítulo se presenta el marco teórico. Primero se describe los antecedentes del estudio de investigación relacionadas a las estaciones macro y sistemas Indoor que se ven involucrados en la estación central del metropolitano, así también la descripción de las bases teóricas vinculadas al problema, se elaboró un glosario de los términos que a la comprensión de la tesis.
En el tercer capítulo se muestra el diseño metodológico, teniendo claro el tipo de investigación que será realizado, así mismo la operacionalización de las variables, que son segmentadas para poder ser medidas y/o controladas, por último la técnica de investigación a realizar.
En el cuarto capítulo se muestra el cronograma de trabajo, aspectos económicos como presupuestos y financiamientos en base a los recursos a utilizar en el estudio.
En el quinto capítulo se muestran las mediciones actuales de los parámetros de cobertura móvil en la estación central del Metropolitano. El sexto capítulo presenta las conclusiones y observaciones de la presente tesis.
This thesis is about the design of a system MIMO using technology DAS (Distributed Antenna System), oriented to an RF Indoor network in the metropolitan central station, improving signal coverage of 2G, 3G and 4G systems.
The thesis is organized as follows:
In the first chapter, the approach of the research study was made identifying existing problems, tracing objectives to be achieved at the end of the thesis. An important part of this chapter is the justification of the study and its importance that it has, this we help us to identify variables to finally have a clear understanding of the problem.
The second chapter presents the theoretical framework. First the background of the research study related to macro-stations and Indoor systems that are involved in the metropolitan central station and also the description of the theoretical basis related to the problem, a glossary of terms was made that support us to the understanding of the thesis.
In the third chapter the methodological design is shown, knowing clearly the type of research to be done, likewise the operationalization of the variables, which are separated with the objective of be measured or controlled. Lastly, investigative technique to perform is shown.
In the fourth chapter, we show the work schedule, budget and economic issues such as financing based on the resources used in the study sample.
In the fifth chapter we show the current measurements of the parameters of mobile coverage in the metropolitan central station. The sixth chapter presents the conclusions and observations of this thesis.
|
142 |
Muse : um ambiente para modelagem de aplicações multimidia interativas com tradutor para e-lotos / MUSE: an interactive multimedia applications specification environment with translator to e-LOTOSGaspary, Luciano Paschoal January 1998 (has links)
É notável o avanço da utilização de aplicações multimídia nos diversos setores da atividade humana. Independente da área, seja ela educação ou entretenimento, a possibilidade de agregar recursos dinâmicos como áudio e vídeo aos já largamente utilizados como texto e imagem acarreta em benefícios aos usuários destas aplicações. Além disso, com a popularização da Internet, ha uma crescente demanda pela sua execução em ambientes distribuídos. Este trabalho teve como objetivo desenvolver MUSE, um ambiente gráfico para modelagem de aplicações multimídia interativas. Através de uma interface gráfica avançada e de um novo modelo de autoria de alto nível, e possível a criação de sistemas complexos de forma rápida e intuitiva. 0 modelo de autoria proposto neste trabalho e adotado pelo ambiente prevê a possibilidade de os elementos que constituem a aplicação estarem dispersos em uma rede de computadores, permitindo a definição de limiares aceitáveis de atraso e componentes alternativos. Pela grande expressividade do modelo, no entanto, podem ser geradas especificações com inconsistências lógicas e temporais. Por esta razão, o ambiente prove ainda especificações E-LOTOS - uma extensão temporal de LOTOS - utilizadas para fins de analise e verificação, permitindo a validação dos requisitos temporais das aplicações definidas pelo autor. A formalização das especificações através de uma TDF, além de viabilizar sua validação, prove descrições sem ambigüidades, que podem ser alternativamente utilizadas por autores que sejam familiarizados com a técnica de descrição formal. Este trabalho é parte do projeto DAMD (Design de Aplicações Multimídia Distribuídas) dentro do programa PROTEM fase 2, que tem por objetivo fornecer uma metodologia que cubra o ciclo completo das aplicações multimídia distribuídas e que permita a um autor não especializado em métodos formais desenvolver essas aplicações naturalmente. / It is notable the advance of multimedia applications utilization in several fields of human activity. Independent from the area, whether education or entertainment, the possibility to aggregate dynamic resources like audio and video to the ones already widely used like text and image results in benefits to the users of such applications. Besides, with the popularization of the Internet, there is an increasing demand for their execution in distributed environments. This work presents MUSE, a graphical environment for modeling interactive multimedia applications. Through an advanced graphic interface and a new high-level authoring model, it is possible to create complex systems in a fast and intuitive way. The authoring model proposed in this work and adopted by the tool deals with media objects distributed in a computer network, allowing the definition of acceptable delay thresholds and alternative media objects. Due to the large expressiveness of the model, however, specifications can be generated with logical and temporary inconsistencies. For this reason, the tool also provides E-LOTOS specifications used with the purpose of analyzing and verifying the applications aiming at validating the temporal requirements defined by the author. The formalization of the specifications by means of a TDF, beyond making their validation possible, provides descriptions free of ambiguities, which may be alternatively used by authors familiarized with the formal description technique. This work is part of DAMD (Distributed Multimedia Applications Design) project, sponsored by the Brazilian research council. Its main objectives are to provide a methodology to completely cover the distributed multimedia applications development cycle and to allow authors who are not expert in formal methods to easily develop their applications.
|
143 |
Dynamic detection of the communication pattern in shared memory environments for thread mapping / Detecção dinâmica do padrão de comunicação em ambientes de memória compartilhada para o mapeamento de threadsCruz, Eduardo Henrique Molina da January 2012 (has links)
As threads de aplicações paralelas cooperam a fim de cumprir suas tarefas, dessa forma, comunicação é realizada entre elas. A latência de comunicação entre os núcleos em arquiteturas multiprocessadas diferem dependendo da hierarquia de memória e das interconexões. Com o aumento do número de núcleos por chip e número de threads por núcleo, esta diferença entre as latências de comunicação está aumentando. Portanto, é importante mapear as threads de aplicações paralelas levando em conta a comunicação entre elas. Em aplicações paralelas baseadas no paradigma de memória compartilhada, a comunicação é implícita e ocorre através de acessos à variáveis compartilhadas, o que torna difícil a descoberta do padrão de comunicação entre as threads. Mecanismos tradicionais usam simulação para monitorar os acessos à memória realizados pela aplicação, requerendo modificações no código fonte e aumentando drasticamente a sobrecarga. Nesta dissertação de mestrado, são introduzidos dois mecanismos inovadores com uma baixa sobrecarga para se detectar o padrão de comunicação entre threads. O primeiro mecanismo faz uso de informações sobre linhas compartilhadas de caches providas por protocolos de coerência de cache. O segundo mecanismo utiliza a Translation Lookaside Buffer (TLB) para detectar quais páginas de memória cada núcleo está acessando. Ambos os mecanismos dependem totalmente do hardware, o que torna o mapeamento de threads transparente aos programadores e permite que ele seja realizado dinamicamente pelo sistema operacional. Além disto, nenhuma tarefa de alta sobrecarga, como simulação, é requerida. As propostas foram avaliadas com o NAS Parallel Benchmarks (NPB), obtendo representações precisas dos padrões de comunicação. Mapeamentos para as threads foram gerados utilizando os padrões de comunicação descobertos e um algoritmo de mapeamento. O problema do mapeamento é NP-Difícil. Portanto, de forma a se atingir uma complexidade polinomial, o algoritmo empregado é heurístico, baseado no algoritmo de emparelhamento de grafos de Edmonds. Executando as aplicações com o mapeamento resultou em um ganho de desempenho de até 15; 3%. O número de faltas na cache, invalidações em linhas de cache e transações de espionagem foram reduzidos em até 31; 9%, 41% e 65; 4%, respectivamente. / The threads of parallel applications cooperate in order to fulfill their tasks, thereby communication is performed among themselves. The communication latency between the cores in a multiprocessor architecture differs depending on the memory hierarchy and the interconnections. With the increase in the number of cores per chip and the number of threads per core, this difference between the communication latencies is increasing. Therefore, it is important to map the threads of parallel applications taking into account the communication between them. In parallel applications based on the shared memory paradigm, the communication is implicit and occurs through accesses to shared variables, which makes difficult to detect the communication pattern between the threads. Traditional approaches use simulation to monitor the memory accesses performed by the application, requiring modifications to the source code and drastically increasing the overhead. In this master thesis, we introduce two novel light-weight mechanisms to find the communication pattern of threads. The first mechanism makes use of the information about shared cache lines provided by cache coherence protocols. The second mechanism makes use of the Translation Lookaside Buffer (TLB) to detect which memory pages each core is accessing. Both our mechanisms rely entirely on hardware features, which makes the thread mapping transparent to the programmer and allows it to be performed dynamically by the operating system. Moreover, no time consuming task, such as simulation, is required. We evaluated our mechanisms with the NAS Parallel Benchmarks (NPB) and obtained accurate representations of the communication patterns. We generated thread mappings from the detected communication patterns using a mapping algorithm. Mapping is a NP-Hard problem. Therefore, in order to achieve a polynomial complexity, we designed a heuristic method based on the Edmonds graph matching algorithm. Running the applications with these mappings resulted in performance improvements of up to 15.3% compared to the original scheduler of the operating system. The number of cache misses, cache line invalidations and snoop transactions were reduced by up to 31.9%, 41% and 65.4%, respectively.
|
144 |
[en] QEEF-G: ADAPTIVE PARALLEL EXECUTION OF ITERATIVE QUERIES / [pt] QEEF-G: EXECUÇÃO PARALELA ADAPTATIVA DE CONSULTAS ITERATIVASVINICIUS FONTES VIEIRA DA SILVA 25 April 2007 (has links)
[pt] O processamento de consulta paralelo tradicional utilize-
se de nós
computacionais para reduzir o tempo de processamento de
consultas. Com o
surgimento das grades computacionais, milhares de nós
podem ser utilizados,
desafiando as atuais técnicas de processamento de consulta
a oferecerem um
suporte massivo ao paralelismo em um ambiente onde as
condições variam todo a
instante. Em adição, as aplicações científicas executadas
neste ambiente oferecem
novas características de processamento de dados que devem
ser integradas em um
sistema desenvolvido para este ambiente. Neste trabalho
apresentamos o sistema
de processamento de consulta paralelo do CoDIMS-G, e seu
novo operador Orbit
que foi desenvolvido para suportar a avaliação de
consultas iterativas. Neste
modelo de execução as tuplas são constantemente avaliadas
por um fragmento
paralelo do plano de execução. O trabalho inclui o
desenvolvimento do sistema de
processamento de consulta e um novo algoritmo de
escalonamento que, considera
as variações de rede e o throughput de cada nó, permitindo
ao sistema se adaptar
constantemente as variações no ambiente. / [en] Traditional parallel query processing uses multiple
computing nodes to
reduce query response time. Within a Grid computing
context, the availability of
thousands of nodes challenge current parallel query
processing techniques to
support massive parallelism in a constantly varying
environment conditions. In
addition, scientific applications running on Grids offer
new data processing
characteristics that shall be integrated in such a
framework. In this work we
present the CoDIMS-G parallel query processing system with
a full-fledged new
query execution operator named Orbit. Orbit is designed
for evaluating massive
iterative based data processing. Tuples in Orbit iterate
over a parallelized
fragment of the query execution plan. This work includes
the development of the
query processing system and a new scheduling algorithm
that considers variation
on network and the throughput of each node. Such algorithm
permits the system
to adapt constantly to the changes in the environment.
|
145 |
[pt] ALGORITMOS ADAPTATIVOS COM EXPLORAÇÃO DE ESPARSIDADE EM REDES DE SENSORES DISTRIBUÍDAS / [en] DISTRIBUTED SPARSITY-AWARE SIGNAL PROCESSING ALGORITHMS FOR SENSOR NETWORKSTAMARA GUERRA MILLER 17 August 2016 (has links)
[pt] Neste trabalho de dissertação são propostos algoritmos adaptativos que
exploram a esparsidade em redes distribuídas de sensores para estimação de
parâmetros e estimação espectral. São desenvolvidos algoritmos gradiente conjugado
(CG) distribuído para os protocolos consenso e difusão em versão
convencional e modificada (MCG). Esses algoritmos são desenvolvidos com
exploração de esparsidade usando as funções penalidades l1 e log-sum. Os
métodos propostos apresentam um melhor desempenho en termos de velocidade
de convergência e desvio médio quadratico (MSD) que as já conhecidas
variantes distribuídas do algoritmo least mean square (LMS) e muito próximo
ao desempenho do algoritmo recursive least square (RLS). Além disso, propõe-se
um algoritmo distribuído de optimização alternada de variáveis discretas e
contínuas (DAMDC) baseado no LMS. O algoritmo DAMDC-LMS apresenta
um desempenho muito próximo ao algoritmo oráculo e tem maior velocidade
de convergência que os algoritmos estudados com exploração de esparsidade.
Os resultados numéricos mostram que o algoritmo DAMDC-LMS pode ser
aplicado em vários cenários. / [en] This dissertation proposes distributed adaptive algorithms exploiting
sparsity for parameter and spectrum estimation over sensor networks. Conventional
and modified conjugate gradient (CG and MCG) algorithms using
consensus and diffusion strategies are presented. Sparsity-aware versions of CG
an MCG algorithms using l1 and log-sum penalty functions are developed. The
proposed sparsity-aware and non-sparse CG and MCG methods outperform
the equivalent variants of the least-mean square (LMS) algorithms in terms of
convergence rate and mean square deviation (MSD) at steady state, and have a
close performance to the recursive least square (RLS) algorithm. The diffusion
CG strategies have shown the best performance, specifically the adapt then
combine (ATC) version. Furthermore a distributed alternating mixed discretecontinuous
(DAMDC) algorithm to approach the oracle algorithm based on the
diffusion strategy for parameter and spectrum estimation over sensor networks
is proposed. An LMS type algorithm with the DAMDC proposed technique obtains
the oracle matrix in an adaptive way and compare it with the existing
sparsity-aware as well as the classical algorithms. The proposed algorithm has
an improved performance in terms of MSD. Numerical results show that the
DAMDC-LMS algorithm is reliable and can be applied in several scenarios.
|
146 |
Automatización de una Subestación Eléctrica utilizando el Protocolo IEC 61850 y el ICCP para el envio de DatosToscano Palacios, Marco Antonio January 2010 (has links)
This thesis report, focuses on the automation process of Electrical Substations, with the main
objective of integration into SCADA systems for electrical equipment responsible for the
operation within substations, these devices have different communication protocols, after
concentration information substation SCADA system, the next step to realize is sending data to
the regulatory body that is in a remote location away from the substation, this is achieved using
communication protocols designed for this function. All this process requires an optimization
for the response times to any event that may happen in the substations and with this an
optimization in operation of generation, distribution and transformation of electrical energy
|
147 |
[en] EFFICIENT FEATURES AND INTERPOLATION DOMAINS IN DISTRIBUTED SPEECH RECOGNITION / [pt] ATRIBUTOS E DOMÍNIOS DE INTERPOLAÇÃO EFICIENTES EM RECONHECIMENTO DE VOZ DISTRIBUÍDOVLADIMIR FABREGAS SURIGUE DE ALENCAR 01 April 2005 (has links)
[pt] Com o crescimento gigantesco da Internet e dos sistemas
de comunicações
móveis celulares, as aplicações de processamento de voz
nessas redes têm
despertado grande interesse . Um problema particularmente
importante nessa área
consiste no reconhecimento de voz em um sistema servidor,
baseado nos
parâmetros acústicos calculados e quantizados no terminal
do usuário
(Reconhecimento de Voz Distribuído). Como em geral estes
parâmetros não são
os mais indicados como atributos de voz para o sistema de
reconhecimento
remoto, é importante que sejam examinadas diferentes
transformações dos
parâmetros, que permitam um melhor desempenho do
reconhecedor. Esta
dissertação trata da extração de atributos de
reconhecimento eficientes a partir dos
parâmetros dos codificadores utilizados em redes móveis
celulares e em redes IP.
Além disso, como a taxa dos parâmetros fornecidos ao
reconhecedor de voz é
normalmente superior àquela com a qual os codificadores
geram os parâmetros, é
importante analisar o efeito da interpolação dos
parâmetros sobre o desempenho
do sistema de reconhecimento, bem como o melhor domínio
sobre o qual esta
interpolação deve ser realizada. Estes são outros tópicos
apresentados nesta
dissertação. / [en] The huge growth of the Internet and cellular mobile
communication systems
has stimulated a great interest in the applications of
speech processing in these
networks. An important problem in this field consists in
speech recognition in a
server system, based on the acoustic parameters calculated
and quantized in the
user terminal (Distributed Speech Recognition). Since these
parameters are not the
most indicated ones for the remote recognition system, it
is important to examine
different transformations of these parameters, in order to
allow a better
performance of the recogniser. This dissertation is
concerned with the extraction
of efficient recognition features from the coder parameters
used in cellular mobile
networks and IP networks. In addition, as the rate that
parameters supplied for the
speech recogniser must be usually higher than that
generated by the codec, it is
important to analyze the effect of the interpolation of the
parameters over the
performance of the recognition system. Moreover, it is
paramount to establish the
best domain over which this interpolation must be carried
out. These are other
topics presented in this dissertation.
|
148 |
[en] DIVISIBLE JOB SCHEDULING IN STAR NETWORKS / [pt] ESCALONAMENTO DE TAREFAS DIVISÍVEIS EM REDES ESTRELAELBIO RENATO TORRES ABIB 03 August 2004 (has links)
[pt] O problema de escalonamento de tarefas divisíveis consiste
em determinar
como uma carga a ser processada deve ser dividida entre
processadores
e em que ordem cada fração de carga será enviada a cada
processador.
Considera-se o escalonamento em redes estrela com
computadores e enlaces
heterogêneos. Nesta dissertação são propostas formulações
originais deste
problema como modelos de programação linear inteira mista,
assim como
um novo algoritmo de complexidade O(n) para a solução ótima
de um
caso especial. Além disso, também são propostas duas novas
heurísticas
para o problema, que permitem a elaboração de bons
escalonamentos para
instâncias de grande porte em um reduzido tempo de
processamento. / [en] The problem of divisible job scheduling consists of
determining how to
divide the data to be processed among processors and in
which order each
fraction should be sent to them. In this dissertation, we
consider the divisible
load scheduling problem in star networks with heterogeneous
computers
and links. Original mixed integer linear programming
formulations of this
problem are proposed, as well as a new algorithm with
complexity O(n)
to find the optimal solution for a special case. We also
propose two fast
heuristics that achieve good results for instances
representing large scale
computing systems.
|
149 |
Grid computing e cloud computing: análise dos impactos sociais, ambientais e econômicos da colaboração por meio do compartilhamento de recursos computacionais / Grid Computing and Cloud Computing: analysis of the social,environmental and economic impacts of the collaboration through the resources sharing.Silva, Diogo Cortiz da 01 October 2009 (has links)
Made available in DSpace on 2016-04-29T14:23:52Z (GMT). No. of bitstreams: 1
Diogo Cortiz Silva.pdf: 1671903 bytes, checksum: ee5719b8fbbb5e1d9a7de4b35b463f43 (MD5)
Previous issue date: 2009-10-01 / This research debates the excess of worldwide available computational resources with
exceeded processing capacity and also how the utilization of the sharing and collaboration
concepts influence the integration of those devices to constitute an economic environment
with high processing capacity. Currently, it is possible to find a great amount of personal
computers, servers and others devices that show high level of idleness, while they could be
being used for another purpose, once there are many scientific researches, collaborative
projects and digital inclusion programs that are short of resources to reach theirs objectives.
The Grid Computing technology was conceived as an alternative to integrate geographically
distributed resources pertaining to different domains, enabling a decentralized computational
environment. The main objective of this research is to analyze how this technology can
generate benefits to the social, environment and economic contexts. In the social approach,
Grid Computing stimulates the collaboration and the sharing of computational resources and
applications, as well as providing features that are very useful for data transparency between
many domains. Those characteristics are also important for the scientific inclusion. The first
Case Study approaches the importance of Grid Computing for the collaborative tasks found in
the scientific project of the Large Hadron Collider (LHC), which allowed many research
institutions and universities around the world to build a shared computational environment of
large scale for processing the data generated by LHC. In the environment context, this
technology also presents some characteristics to make the computational resources more
energy efficient increasing the use of its computational capacities. The second Case Study
analyzes the data related to the amount of personal computers connected in the Internet and
how to implement Grid Computing based on the Volunteer Computing model to make those
computers more productive with no relevant impact in the energy consumption. This research
also highlights the synergy between Grid Computing and Cloud Computing, its financial
advantages and the generation of new business models based on the commercialization of
platform and software as a service in the Internet. The third Case Study analyzes a Cloud
Computing model that delivers computational resources (such as a whole server) as a service,
enabling a scenario where companies and people could contract a computational environment
with a quick provisioning with no need to purchase equipments and to invest in
implementation projects. Finally, it is possible to appoint both technologies as relevant trends
for the coming years, which can be an influence to generate new software models, platforms
and services focused in the Internet / Esta dissertação discute o excesso de recursos computacionais disponíveis mundialmente com
capacidade de processamento excedente e também debate como o emprego dos conceitos de
compartilhamento e colaboração influenciam a integração desses dispositivos para constituir
um ambiente econômico e com alta capacidade de processamento. Atualmente, é possível
encontrar uma grande quantidade de computadores pessoais, servidores, entre outros
dispositivos, que apresentam elevados níveis de ociosidade. Estes poderiam ser utilizados para
outra finalidade, haja vista pesquisas científicas, projetos colaborativos e programas de
inclusão digital carentes de recursos para atingirem seus objetivos. A tecnologia de Grid
Computing, também chamada de Computação em Grade, foi concebida como uma alternativa
para integrar recursos distribuídos geograficamente e pertencentes a diferentes domínios,
habilitando um ambiente computacional abrangente e descentralizado. O objetivo desta
dissertação é analisar como essa tecnologia, baseada no conceito de colaboração, pode gerar
benefícios no contexto social, ambiental e econômico. No âmbito social, Grid Computing
estimula o trabalho colaborativo e o compartilhamento de recursos computacionais e
aplicacões, além de prover funcionalidades que auxiliam na transparência de dados entre
diversos domínios. Essas características também são importantes para a inclusão científica. O
primeiro Estudo de Caso aborda a importância de Grid Computing para o projeto científico do
Superacelerador de Partículas (LHC). No contexto ambiental, essa tecnologia também
apresenta características para tornar os recursos computacionais mais eficientes em relação ao
consumo de energia através do aumento do uso de sua capacidade computacional. O segundo
Estudo de Caso aborda dados em relação à quantidade de máquinas conectadas à Internet e
como uma aplicação de Grid Computing, no modelo de Computação Voluntária, pode tornálas
mais produtivas e, consequentemente, mais eficientes no consumo de recursos energéticos.
Já no contexto econômico, é de importância destacar a sinergia existente entre Grid
Computing e Cloud Computing, as suas vantagens financeiras e a geração de novos modelos
de negócios através da comercialização de plataformas e softwares como serviços na Internet,
e não mais como produtos. O terceiro Estudo de Caso aborda um modelo de Cloud
Computing que disponibiliza recursos computacionais em forma de serviços, permitindo que
empresas e pessoas físicas possam contratar um ambiente computacional de rápido
provisionamento, sem a necessidade de adquirir equipamentos e investir em projetos de
implementação. Por fim, ambas as tecnologias são apontadas como grandes tendências para
os próximos anos, as quais influenciarão a geração de novos modelos de softwares,
plataformas e serviços voltados à Internet
|
150 |
Analysis of synchronizations in greedy-scheduled executions and applications to efficient generation of pseudorandom numbers in parallel / Análise de sincronizações em execuções por escalonamento guloso e aplicações para geração eficiente de números pseudoaleatórios em paralelo / Analyse des synchronisations dans un programme parallèle ordonnancé par vol de travail applications à la génération déterministe de nombres pseudo-aléatoiresMor, Stefano Drimon Kurz January 2015 (has links)
Nous présentons deux contributions dans le domaine de la programmation parallèle. La première est théorique : nous introduisons l’analyse SIPS, une approche nouvelle pour dénombrer le nombre d’opérations de synchronisation durant l’exécution d’un algorithme parallèle ordonnancé par vol de travail. Basée sur le concept d’horloges logiques, elle nous permet : d’une part de donner de nouvelles majorations de coût en moyenne; d’autre part de concevoir des programmes parallèles plus efficaces par adaptation dynamique de la granularité. La seconde contribution est pragmatique : nous présentons une parallélisation générique d’algorithmes pour la génération déterministe de nombres pseudo-aléatoires, indépendamment du nombre de processus concurrents lors de l’exécution. Alternative à l’utilisation d’un générateur pseudo-aléatoire séquentiel par processus, nous introduisons une API générique, appelée Par-R qui est conçue et analysée grâce à SIPS. Sa caractéristique principale est d’exploiter un générateur séquentiel qui peut “sauter” directement d’un nombre à un autre situé à une distance arbitraire dans la séquence pseudo-aléatoire. Grâce à l’analyse SIPS, nous montrons qu’en moyenne, lors d’une exécution par vol de travail d’un programme très parallèle (dont la profondeur ou chemin critique est très petite devant le travail ou nombre d’opérations), ces opérations de saut sont rares. Par-R est comparé au générateur pseudo-aléatoire DotMix écrit pour Cilk Plus, une extension de C/C++ pour la programmation parallèle par vol de travail. Le surcout théorique de Par-R se compare favorablement au surcoput de DotMix, ce qui apparait aussi expériemntalement. De plus, étant générique, Par-R est indépendant du générateur séquentiel sous-jacent. / Nós apresentamos duas contribuições para a área de programação paralela. A primeira contribuição é teórica: nós introduzimos a análise SIPS, uma nova abordagem para a estimar o número de sincronizações realizadas durante a execução de um algoritmo paralelo. SIPS generaliza o conceito de relógios lógicos para contar o número de sincronizações realizadas por um algoritmo paralelo e é capaz de calcular limites do pior caso mesmo na presença de execuções paralelas não-determinísticas, as quais não são geralmente cobertas por análises no estado-da-arte. Nossa análise nos permite estimar novos limites de pior caso para computações escalonadas pelo popular algoritmo de roubo de tarefas e também projetar programas paralelos e adaptáveis que são mais eficientes. A segunda contribuição é pragmática: nós apresentamos uma estratégia de paralelização eficiente para a geração de números pseudoaleatórios. Como uma alternativa para implementações fixas de componentes de geração aleatória nós introduzimos uma API chamada Par-R, projetada e analisada utilizando-se SIPS. Sua principal idea é o uso da capacidade de um gerador sequencial R de realizar um “pulo” eficiente dentro do fluxo de números gerados; nós os associamos a operações realizadas pelo escalonador por roubo de tarefas, o qual nossa análise baseada em SIPS demonstra ocorrer raramente em média. Par-R é comparado com o gerador paralelo de números pseudoaleatórios DotMix, escrito para a plataforma de multithreading dinâmico Cilk Plus. A latência de Par-R tem comparação favorável à latência do DotMix, o que é confirmado experimentalmente, mas não requer o uso subjacente fixado de um dado gerador aleatório. / We present two contributions to the field of parallel programming. The first contribution is theoretical: we introduce SIPS analysis, a novel approach to estimate the number of synchronizations performed during the execution of a parallel algorithm. Based on the concept of logical clocks, it allows us: on one hand, to deliver new bounds for the number of synchronizations, in expectation; on the other hand, to design more efficient parallel programs by dynamic adaptation of the granularity. The second contribution is pragmatic: we present an efficient parallelization strategy for pseudorandom number generation, independent of the number of concurrent processes participating in a computation. As an alternative to the use of one sequential generator per process, we introduce a generic API called Par-R, which is designed and analyzed using SIPS. Its main characteristic is the use of a sequential generator that can perform a “jump-ahead” directly from one number to another on an arbitrary distance within the pseudorandom sequence. Thanks to SIPS, we show that, in expectation, within an execution scheduled by work stealing of a “very parallel” program (whose depth or critical path is subtle when compared to the work or number of operations), these operations are rare. Par-R is compared with the parallel pseudorandom number generator DotMix, written for the Cilk Plus dynamic multithreading platform. The theoretical overhead of Par-R compares favorably to DotMix’s overhead, what is confirmed experimentally, while not requiring a fixed generator underneath.
|
Page generated in 0.0608 seconds