Dissertations / Theses on the topic 'Parallel prefix'

Fast addition is essential in many DSP algorithms. Various structures have been introduced to speed up the time critical carry propagation. For high throughput applications, however, it may be necessary to introduce pipelining. In this report the power consumption of four different adder structures, with varying word length and different number of pipeline cuts, is compared.

Out of the four adder structures compared, the Kogge-Stone parallel prefix adder proves to be the best choice most of the time. The Brent-Kung parallel prefix adder is also a good choice, but the maximal throughput does not reach as high as the maximal throughput of the Kogge-Stone parallel prefix adder.

Made available in DSpace on 2017-07-21T14:19:32Z (GMT). No. of bitstreams: 1 AdrianoSerckumecka.pdf: 825262 bytes, checksum: 9c527c3f506be1e58cf82ac8117dac67 (MD5) Previous issue date: 2012-07-17
The main objective of this work is the evaluation of distributed systems based on peer-topeer network and parallel computing techniques to reduce response times of climate simulations. A probabilistic model for simulating wind data was used and two computing applications was implemented and evaluated. The first application was developed by using the framework P2PComp, which is directed to building parallel software and its deploy in P2P networks. The second application was developed without the support of this framework and using straightly the communication infrastructure software. Climatic data of the municipality of Lapa, Paraná comprising the period between 1998 and 2007 were used in the experiments. The results demonstrate the feasibility of using parallel computing and P2P networks for executing climate simulations. Best results, measured by the speedup obtained, were observed when using multiple peers (equal to 26) and when executing simulations for a long period of time ( near to 100 years). In such case, the speedup obtained is near to 7.
O objetivo principal deste trabalho é a avaliação de sistemas distribuídos baseados em redespar-a-par (P2P), juntamente com técnicas de computação paralela, para reduzir os tempos deresposta de simulações climáticas. Um modelo probabilístico específico para simulação de dados de vento foi adotado e duas aplicações computacionais foram implementadas e avaliadas.A primeira aplicação foi desenvolvida com o uso do Framework P2PComp, que permite a criação de programas paralelos e sua execução em redes P2P. A segunda aplicação adotou diretamente uma rede P2P, sem o uso desse framework, como infraestrutura de comunicação.Dados climáticos da região do Município de Lapa-PR, compreendendo o períıodo entre 1998 e 2007 foram empregados nos experimentos. Os resultados obtidos demonstram a viabilidade de utilização de computação paralela em redes P2P, nas simulações climáticas. Os melhores resultados medidos em relação ao fator de aceleração foram observados em situações onde foi utilizado um número maior de pares (igual a 26) e simulações climáticas para um período de tempo igual a 100 anos. Para este caso, o fator de aceleração obtido foi aproximadamente igual a 7.

Made available in DSpace on 2017-07-21T14:19:39Z (GMT). No. of bitstreams: 1 Ciro Baron Neto.pdf: 1513768 bytes, checksum: a9f4624d5d9521cfa109fa40a688cbb2 (MD5) Previous issue date: 2014-02-28
This paper presents an approach of technologies GPGPU (General-Purpose Computing on Graphics Processing Unit) and P2P (peer-to-peer) networks in order to improve the response time of climate data simulations. Thus, an application using CUDA (Compute Unified Device Architecture) architecture and the simulation model of Venthor simulator were initially adopted and integrated into the P2PComp framework. The results indicate an acceleration factor equal to 70 for single computers. Furthermore, the possibility of using a P2P sharing network for processing, higher acceleration factors can be obtained. Computer simulation models usually demand high processing power and this work showed that the use of parallelism in GPUs and P2P networks is an alternative that allows better performance when compared to sequential computing.
Este trabalho apresenta uma avaliação das tecnologias de GPGPU (General-Purpose Computing on Graphics Processing Unit) e de redes P2P (peer-to-peer) para melhorar o tempo de resposta de simulações de dados climáticos. Para isso, uma aplicação utilizando a arquitetura CUDA (Compute Unified Device Architecture) e o modelo de simulação de dados de vento do software Venthor foram inicialmente adotados e após integrados ao framework P2PComp. Os resultados indicam um fator de aceleração igual a 70 para computadores isolados. Além disso, com a possibilidade do uso de uma rede P2P para compartilhamento de processamento, fatores de aceleração maiores podem ser obtidos. Modelos de simulação computacional geralmente demandam alto poder de processamento e este trabalho mostrou que a utilização do paralelismo em redes P2P e GPUs constitui uma alternativa que permite melhor desempenho quando comparado à computação sequencial.

Den här studien undersöker det ryska verbprefixet v(o)- och cirkumfixet v(o)- -sja i det konkreta fysiska rummet. Syftet med den kontrastiva studien är att undersöka och beskriva betydelser. Tvåspråkig data från en samtida rysk-svensk ordbok analyseras med Krongauz metod. En lista över verbaffixens betydelser byggs upp genom att jämföra lexikala betydelser och morfosyntaktiska konstruktioner för verben i båda språken. Resultatet visar att affixens betydelser kan delas in i följande kategorier: Spatiala rörelser in i ett slutet rum, Spatiala rörelser till en avgränsad yta, Spatiala rörelser mot en närhet, Vidhäftning och Platser i det fysiska rummet.
This present study investigates the Russian verbal prefix v(o)- and circumfix v(o)- -sja in the concrete physical space. The aim of the contrastive study is to explore and describe meanings. Bilingual data, extracted from a contemporary Russian-Swedish dictionary, is analysed by using Krongauz’s method. A list of meanings of the Russian verbal affixes is built by comparing similarities and differences between lexical meanings and morphosyntactic structures for the verbs in both languages. The result shows that the meanings of the affixes can be divided into the following categories: Spatial movements into an enclosed space, Spatial movements onto a delimited surface, Spatial movements towards a vicinity, Adhesion and Locations in physical space.

Made available in DSpace on 2017-07-21T14:19:24Z (GMT). No. of bitstreams: 1 Lays Veloso.pdf: 1140015 bytes, checksum: c544c69a03612a2909b7011c936788ee (MD5) Previous issue date: 2015-04-29
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
This study aimed to investigate the use of a parallel K-means clustering algorithm,based on parallel MapReduce model, to improve the response time of the data mining. The parallel K-Means was implemented in three phases, performed in each iteration: assignment of samples to groups with nearest centroid by Mappers, in parallel; local grouping of samples assigned to the same group from Mappers using a Combiner and update of the centroids by the Reducer. The performance of the algorithm was evaluated in respect to SpeedUp and ScaleUp. To achieve this, experiments were run in single-node mode and on a Hadoop cluster consisting of six of-the-shelf computers. The data were clustered comprise flux towers measurements from agricultural regions and belong to Ameriflux. The results showed performance gains with increasing number of machines and the best time was obtained using six machines reaching the speedup of 3,25. To support our results, ANOVA analysis was applied from repetitions using 3, 4 and 6 machines in the cluster, respectively. The ANOVA show low variance between the execution times obtained for the same number of machines and a significant difference between means of each number of machines. The ScaleUp analysis show that the application scale well with an equivalent increase in data size and the number of machines, achieving similar performance. With the results as expected, this paper presents a parallel and scalable implementation of the K-Means to run on a Hadoop cluster and improve the response time of clustering to large databases.
Este trabalho teve como objetivo investigar a utilização de um algoritmo de agrupamento K-Means paralelo, com base no modelo paralelo MapReduce, para melhorar o tempo de resposta da mineração de dados. O K-Means paralelo foi implementado em três fases, executadas em cada iteração: atribuição das amostras aos grupos com centróide mais próximo pelos Mappers, em paralelo; agrupamento local das amostras atribuídas ao mesmo grupo pelos Mappers usando um Combiner e atualização dos centróides pelo Reducer. O desempenho do algoritmo foi avaliado quanto ao SpeedUp e ScaleUp. Para isso foram executados experimentos em modo single-node e em um cluster Hadoop formado por seis computadores de hardware comum. Os dados agrupados são medições de torres de fluxo de regiões agrícolas e pertencem a Ameriflux. Os resultados mostraram que com o aumento do número de máquinas houve ganho no desempenho, sendo que o melhor tempo obtido foi usando seis máquinas chegando ao SpeedUp de 3,25. Para apoiar nossos resultados foi construída uma tabela ANOVA a partir de repetições usando 3, 4 e 6 máquinas no cluster, pespectivamente. Os resultados da análise ANOVA mostram que existe pouca variância entre os tempos de execução obtidos com o mesmo número de máquinas e existe uma diferença significativa entre as médias para cada número de máquinas. A partir dos experimentos para analisar o ScaleUp verificou-se que a aplicação escala bem com o aumento equivalente do tamanho dos dados e do número de máquinas no cluster,atingindo um desempenho próximo. Com os resultados conforme esperados, esse trabalho apresenta uma implementação paralela e escalável do K-Means para ser executada em um cluster Hadoop e melhorar o tempo de resposta do agrupamento de grandes bases de dados.

Made available in DSpace on 2017-07-21T14:19:37Z (GMT). No. of bitstreams: 1 Cristian Abreu.pdf: 2219271 bytes, checksum: 3d770700a8027fff9a36f6287c8c4e54 (MD5) Previous issue date: 2013-04-30
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
The objective of this study was investigate the use of parallel computing to reduce the response time of data mining in agriculture. For this purpose, a tool, called Fast Weka been defined and implemented. This tool allows running data mining algorithms and explore parallelism in multi-core computers with the use of threads and distributed systems employing peer-to-peer networks. The exploration of parallelism occurs through the data parallelism inherent to the process of cross-validation (folds). The tool was evaluated through experiments using artificial neural networks data mining algorithms applied to a data set of forest cover types. The multi-thread computing and computing on peer-to-peer networks allowed to reduce the response time of data mining activities. The best results were achieved when employed a multiple number of threads or pairs in the number of folds of cross validation. It was observed and efficiency of 87% when used 4 threads to 24 folds and 86% efficiency also in peer-to-peer networks using 24 folds with 11 pairs.
O objetivo deste trabalho foi investigar a utilização da computação paralela para reduzir o tempo de resposta da mineração de dados na agricultura. Para esse fim, uma ferramenta, chamada Fast Weka foi definida e implementada. Essa ferramenta permite executar algoritmos de mineração de dados e explorar o paralelismo em computadores multi-núcleos com uso de threads em sistemas distribuídos empregando redes peer-to-peer. A exploração do paralelismo ocorre por meio do paralelismo de dados inerente ao processo de validação cruzada (folds). A ferramenta foi avaliada por meio de experimentos de mineração de dados utilizando algoritmos de redes neurais artificiais aplicados em um conjunto de dados de tipos de coberturas florestais. A computação multi-thread e a computação em redes peer-to-peer permitiram reduzir o tempo de resposta das atividades de mineração de dados. Os melhores resultados foram obtidos quando empregados um número múltiplo de threads ou pares em relação ao número de folds da validação cruzada. Observou-se uma eficiência de 87% quando utilizadas 4 threads para 24 folds e 86% de eficiência, também, com 2 folds utilizando redes peer-to-peer co 11 pares.

Made available in DSpace on 2017-07-21T14:19:25Z (GMT). No. of bitstreams: 1 Andrey Orloski.pdf: 5923583 bytes, checksum: 1a18c76b30193410838467808e3fa40d (MD5) Previous issue date: 2015-09-04
This paper describes a procedure for self-localization of mobile and autonomous agrobots in greenhouses, that is, the determination of the robot's position relative to a coordinate system,using procedures and computational resources. The proposed procedure uses computer vision techniques to recognize markers objects in the greenhouse and, from them, estimate the coordinate of the robot in a parallel plane to the surface of the stove. The detection of the presence of markers in the scene is performed using the SURF algorithm. To enable the estimation of coordinates, based on data contained in a single image, the method of Rahman et al. (2008), which consists in etermining the distance between a camera and a marker object has been extended to allow the coordinate calculation. The performance of the procedure was evaluated in three experiments. In the first experiment, the objective was to verify, in the laboratory, the influence of image resolution on accuracy. The results indicate that by reducing the image resolution, the range of the process is impaired for the recognition of the markers. These results also show that by reducing the resolution, the error in estimating the coordinates relative to the distance between the camera and the marker increases. The second experiment ran a test that evaluates the computational performance of the SURF algorithm, in terms of computing time, in the image processing. This is important because agrobots usually need to perform tasks that require the processing power in real time. The results of this test indicate that the efficiency of the procedure drops with the increase of image resolution. A second test compared the processing time of two implementations of the algorithm. One explores a sequential version of the SURF algorithm and another uses a parallel implementation. The results of this test suggest that the parallel implementation is more efficient in all tested resolutions, with an almost constant proportionate improvement.The third experiment was performed in a greenhouse to evaluate the performance of the proposed procedure in the environment for which it was designed. Field results were similar to the laboratory, but indicate that lighting variations require parameter settings of the SURF algorithm.
Este trabalho descreve um procedimento para autolocalização de agrobots móveis e autônomos em casas de vegetação. Isto é, a determinação da posição do robô em relação a um sistema de coordenadas, usando procedimentos e recursos computacionais. O procedimento proposto emprega técnicas de visão computacional para reconhecer objetos marcadores na casa de vegetação e, a partir deles, estimar a coordenada do robô em um plano paralelo a superfície da estufa. A detecção da presença dos marcadores na cena é realizada através do algoritmo SURF. Para viabilizar a estimativa das coordenadas, a partir de dados contidos em uma única imagem, o método de Rahman et al. (2008), que consiste em determinar a distância entre uma câmera e um objeto marcador, foi estendido para permitir o cômputo de coordenadas. O desempenho do procedimento proposto foi avaliado em três experimentos. No primeiro experimento, o objetivo foi verificar, em laboratório, a influência da resolução da imagem sobre a precisão. Os resultados indicam que, ao reduzir a resolução da imagem, o alcance do procedimento é prejudicado para reconhecimento dos marcadores. Estes resultados também mostram que, ao reduzir a resolução, o erro na estimativa das coordenadas em relação à distância entre a câmera e o marcador aumenta. O segundo experimento executou um teste que avalia o desempenho computacional do algoritmo SURF, em termos de tempo de computação, no processamento das imagens. Isto é importante pois agrobots usualmente precisam executar tarefas que demandam capacidade de processamento em tempo real. Os resultados deste teste indicam que a eficiência do procedimento cai com o aumento da resolução da imagem. Um segundo teste comparou o tempo de processamento de duas implementações do algoritmo. Uma que explora uma versão sequencial do algoritmo SURF e outra que usa uma implementação paralela. Os resultados deste teste sugerem que a implementação paralela foi mais eficiente em todas as resoluções testadas, apresentando uma melhora proporcional quase constante. O terceiro experimento foi realizado em uma casa de vegetação com objetivo de avaliar o desempenho do procedimento proposto no ambiente para o qual foi projetado. Os resultados de campo se mostraram semelhantes aos do laboratório, mas indicam que variações de iluminação exigem ajustes de parâmetros do algoritmo SURF.

Submitted by Eunice Novais (enovais@uepg.br) on 2017-08-17T19:02:15Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) FABIANA FERNANDES MADALOZZO COPPLA.pdf: 8129839 bytes, checksum: 555584401fddabd5299b0abdea4be4de (MD5)
Made available in DSpace on 2017-08-17T19:02:15Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) FABIANA FERNANDES MADALOZZO COPPLA.pdf: 8129839 bytes, checksum: 555584401fddabd5299b0abdea4be4de (MD5) Previous issue date: 2017-06-28
Introdução: A Sensibilidade dental (SD) induzida pelo clareamento é altamente prevalente. A combinação de opioides e analgésicos não opioides pode proporcionar um melhor efeito analgésico. Objetivos: Avaliar o efeito da associação de paracetamol / codeína administrado pré e pós-operatoriamente sobre o risco e a intensidade da SD induzida pelo clareamento dental. Métodos: Realizou-se um ensaio clínico randomizado paralelo, triplo cego, com 105 pacientes saudáveis os quais receberam um placebo ou uma associação de paracetamol / codeína. A primeira dose de (paracetamol 500 mg / codeína 30 mg) ou placebo foi administrada 1 h antes do clareamento em consultório (peróxido de hidrogénio 35%) e doses extras foram administradas a cada 6 h durante 48 h. A SD foi avaliada utilizando duas escalas: 0-10 escala visual analógica VAS e uma escala de classificação numérica NRS 0-4 em diferentes períodos: durante o clareamento, 1 h até 24 h, 24 h até 48 h pós clareamento. A cor foi mensurada antes e um mês após o clareamento dental com uma escala de cores visuais Vita Classical, Vita Bleachedguide 3D-Master e espectrofotômetro Vita Easyshade (Vita Zahnfabrik). O risco absoluto de SD foi avaliado pelo teste exato de Fisher. Os dados da intensidade SD com escala NRS dos dois grupos foram comparados com os testes de Mann- Whitney e Friedman, enquanto que os dados da escala VAS foram avaliados por meio de ANOVA dois fatores de medidas repetidas. As alterações de cor entre os grupos foram comparadas utilizando teste t de Student (α = 0,05). Resultados: Não foram observadas diferenças significativas entre os grupos quanto ao risco e intensidade de SD. O risco absoluto total de SD foi de aproximadamente 96%. Uma alteração de cor de quase 5 unidades da escala de cor visual Vita Classical foi detectada em ambos os grupos, que foram estatisticamente semelhantes (p> 0,05). Conclusão: O uso da associação paracetamol / codeína pré e pós clareamento de consultório não reduz o risco e a intensidade da SD induzida pelo clareamento. Implicações clínicas: O uso de um fármaco analgésico opioide não foi capaz de prevenir SD decorrente de clareamento dental em consultório.
Background: Bleaching-induced TS is highly prevalent. The combination of Opioids and non opioids analgesics may provide a better analgesic effect. Objective: To evaluate the effect of the combination of paracetamol / codeine administered before and postoperatively on the risk and intensity of TS induced by dental whitening. Methods: A triple-blind, parallel, randomized clinical trial was conducted with 105 health patients who received either a placebo or an association of codeine/acetaminophen. The first dose of Tylex® 30 mg (acetaminophen 500 mg/codeine 30 mg) or placebo was administered 1 h before the in-office bleaching (35% hydrogen peroxide), and extra doses were administered every 6 h for 48 h. The TS was recorded using two scales: 0-10 visual analog scale and a 0-4 numeric rating scale in different periods: during bleaching, 1 h up to 24 h, 24 h up to 48 h postbleaching. The color was measured before and one month after dental bleaching with a visual shade guide Vita Classical, Vita Bleachedguide 3D-Master and spectrophotometer Vita Easyshade (Vita Zahnfabrik). The absolute risk of TS was evaluated by Fisher’s exact test. Data of TS intensity with NRS scale of the two groups were compared with Mann-Whitney and Friedman tests, while data from the VAS scale were evaluated by two-way repeated measures ANOVA. The color changes between groups were compared using a Student t-test (α = 0.05). Results: No significant differences between the groups were observed in the risk and intensity of TS. The overall absolute risk of TS was approximate 96%. A color change of nearly 5 shade guide units of the Vita Classical was detected in both groups, which were statistically similar (p > 0.05). Conclusion: The use of acetaminophen/codeine association pre and post in-office bleaching does not reduce the risk and intensity of bleaching-induced TS. Practical Implications: The use of an opioid analgesic drug was not capable to prevent TS arising from in-office dental bleaching.

Os prefixos germânicos de alguns verbos suecos serão comparados numa análise contrastiva com as relativas equivalências em português e em italiano num corpus paralelo escrito composto por um romance de língua sueca, um de língua portuguesa e um de língua italiana e pelas suas respectivas traduções. As funções desenvolvidas pelos prefixos germânicos dos verbos suecos analisados serão examinadas e depois confrontadas com as relativas equivalências, com o resultado que também nas duas línguas românicas relevam-se, de maneira bastante constante, procedimentos gramaticais parecidos aos desenvolvidos pelos prefixos germânicos.
Germanic prefixes of which some Swedish verbs are composed are going to be compared in acontrastive analysis with their relative equivalences in Portuguese and Italian in a parallel written corpus characterized by a Swedish-language romance, a Portuguese-language romance and an Italian language romance, and by their relative translations. The functions executed by the German prefixes of the analysed Swedish verbs are going to be examined and then compared with their relative equivalences, with the result that even in the Romance languages it is possible to find in a quite constant way grammatical processes which are similar to those executed by the Germanic prefixes.
I prefissi germanici di alcuni verbi svedesi saranno comparati in un'analisi contrastiva con le relative equivalenze in portoghese e in italiano in un corpus parallelo scritto composto da un romanzo di lingua svedese, uno di lingua portoghese e uno di lingua italiana e dalle rispettive traduzioni. Le funzioni svolte dai prefissi germanici dei verbi svedesi analizzati saranno esaminate e poi confrontate con le relative equivalenze, con il risultato che anche nelle due lingue romanze si riscontrano in maniera abbastanza costante processi grammaticali simili a quelli svolti dai prefissi germanici.
De germanska prefix som återfinns i vissa svenska verb kommer att jämföras med sina motsvarigheter på portugisiska och italienska. Detta görs med hjälp av en skriven korpus bestående av en roman ursprungligen skriven på svenska, en skriven på portugisiska och en skriven på italienska samt översättningar av dessa romaner till de två andra språken. Funktionen hos de svenska verben med germanska prefix kommer att analyseras och sedan jämföras med verbens motsvarigheter. Resultatet av analysen visar att det är möjligt att finna systematiskt återkommande grammatiska processer i de romanska språken, som liknar de som förekommer i samband med de germanska prefixen på svenska.

碩士
國立臺灣科技大學
資訊工程系
97
Give n values x1, x2,…, xn and an associative binary operation ♁, the prefix computation is to compute x1 ♁ x2 ♁…♁ xi, 1 ≤ i ≤ n. Because prefix computation has many applications, a large number of algorithms, called parallel prefix algorithms, have been developed to solve the prefix problem. Although some previous parallel prefix algorithms provide the flexibility of choosing parameter values to achieve less running time, they may have only few viable parameter values in some cases. Hence, we have improved a previous algorithm for the message-passing multicomputer to solve the drawback. It can thus be faster than previous algorithms when appropriate parameter values are used. We have also derived the number of computation steps and that of communication steps of the new algorithm. The precondition of this algorithm is also derived.

碩士
國立臺灣科技大學
電子工程系
89
Give n values x1, x2,…, xn and an associative binary operation ⊕ the prefix operation is to compute x1⊕x2⊕…⊕xi, 1≤i≤n. Because prefix computation has many applications, a great number of combinational circuits, called prefix circuits, have been designed to solve the prefix problem. For any prefix circuit D with n inputs, the depth d(D) and the size s(D) satisfy the inequality d(D) + s(D) ≥ 2n - 2; thus, if d(D) + s(D) = 2n - 2, D is depth-size optimal. In general, a prefix circuit with a smaller depth is faster. For prefix circuits with the same depth, the prefix circuit that has a smaller fan-out occupies less VLSI area and is faster. Thus, the depth and fan-out of a prefix circuit should be as small as possible. In this thesis, we construct a depth-size optimal prefix circuit Z4 with fan-out 4, and its depth is between 2┌log n┐-6 and 2┌log n┐-3. Compared with another depth-size optimal prefix circuit WE4 with fan-out 4, the depth of Z4 may be less than or greater than that of WE4. The depth of Z4 is smaller than all the other known prefix circuits with fan-out 4. Compared with QL, a depth-size optimal prefix circuit with unbounded fan-out, the depth of Z4 may be equal to or greater than that of QL; however, because the fan-out of Z4 is smaller than that of QL, Z4 may be faster and its VLSI area is smaller.

碩士
國立臺灣科技大學
電子工程系
89
Give n values x1, x2,..., xn and an associative binary operation , the prefix problem is to computex1, x2,..., xi,1≦i≦n.　Because prefix computation has many applications, many combinational circuits for solving the prefix problem, called prefix circuit, has been designed.　The depth d(D) and the size s(D) of an n-input prefix circuit D satisfy d(D) + s(D) ≧2n - 2; thus, the prefix circuit is depth-size optimal if d(D) + s(D) = 2n - 2. A prefix circuit with a smaller size requires less VLSI area, and one with smaller depth is faster. In addition, a node with a greater fan-out is slower and requires larger VLSI area. In this thesis, we construct a depth-size optimal parallel prefix circuit WE4 with fan-out 4, the depth of WE4 between 2log n-6 and 2log n-3.Compared with another depth- size optimal prefix circuit Z4, the depth of WE4 may be less than or greater than that of Z4. The depth of WE4 is smaller than all the other known prefix circuits with fan-out 4.　 Compared with QL, a depth-size optimal prefix circuit with unbounded fan-out, WE4 may have may a greater or equal depth than QL; however, because the fan-out of WE4 is smaller than that of QL, the VLSI area of WE4 is smaller, and WE$ may be faster.

博士
國立臺灣科技大學
電子工程系
89
Give n values x1, x2,..., xn and an associative binary operation ⊕, the prefix problem is to compute x1 ⊕x2 ⊕...⊕xi, 1<=i<=n. Because prefix computation has numerous applications, many combinational circuits for solving the prefix problem, called prefix circuits, have been designed. The depth d(D(n)) and the size s(D(n)) of an n-input prefix circuit D(n) satisfy d(D(n)) + s(D(n)) >=2n—2; thus, the prefix circuit is depth-size optimal if d(D(n)) + s(D(n)) = 2n—2. A prefix circuit with a larger size requires a larger VLSI area, and one with a greater depth is slower. In addition, a node with a greater fan-out is slower and requires a larger VLSI area. In this thesis, we first construct two prefix circuits with bounded fan-out Q and T. All the known depth-size optimal prefix circuits with fan-out 4 consist of Q. We also compose depth-size optimal prefix circuits. The prefix circuits SL and QL have unbounded fan-out; F4 and L3_4 have a fan-out of at most 4; and L3 has a fan-out of 3. QL(n) is the depth-size optimal parallel prefix circuit with the smallest depth among all known depth-size optimal parallel prefix circuits, and 2┌log n┐-8<=d(QL(n))<=2┌log n┐-4. Furthermore, we present a constant-time algorithm for finding depth-size optimal parallel prefix circuits with fan-out 3 or 4 and depth t, d(F4(n)) < t < n — 1.

碩士
國立東華大學
資訊工程學系
87
We employ a methodology to solving parallel prefix problems by using a tensor product notation. Tensor product notation is suitable to express block-recursive algorithms, data distribution, and interconnection networks. Tensor product operations can be mapped into corresponding programming constructs. Hence, it provides a framework of designing and implementing parallel programs. In this paper, a parallel prefix algorithm is specified as a tensor product formula which is then translated into parallel programs for various computer architectures. These architectures may include vector processors, shared-memory multiprocessors, and distributed-memory multiprocessors.

碩士
國立臺灣科技大學
電子工程系
92
Given n values x1, x2,, xn, and an associative binary operation , the prefix operation is to compute x1  x2  xi, 1 ≤ i ≤ n. Because the prefix computation has many applications, many combinational circuits for performing the prefix operation, called prefix circuits, have been designed. For any prefix circuit D, the depth d(D) and the size s(D) satisfy d(D) + s(D) ≥ 2n — 2; thus, if d(D) + s(D) = 2n — 2, D is depth-size optimal. Among prefix circuits with the same fan-out, a circuit with a smaller depth should be faster. In this thesis, we define the level-by-level composition of two prefix circuits and present a new algorithm. With this new algorithm, we construct three size-optimal prefix circuits TM, TY, and TJ. Then we use TM, TY, TJ together with other existing prefix circuits. to compose an optimal prefix circuit JM4, which has a depth between 2 lg n — 8 and 2 lg n — 4. The depth of JM4 is smaller than that of any other previously known depth-size optimal prefix circuits with fan-out 4.

博士
國立交通大學
資訊工程研究所
83
In this dissertation, we study parallel prefix computation and its applications. Parallel prefix computation has been widely discussed since 1980. Here, we focus on prefix computation on some array processors such as complete graphs, hypercubes, trees, and 2-MCCMB''s. First, we propose a new model: non- associative prefix computation. Associativity of a binary operation allows many applications that are not possible with a non-associative binary operation. So we propose a method to transform a binary expression into an associative one, then compute prefixes by using associative prefix computation. Two applications about non-associative prefix computation are also presented: linear recurrences and carry-lookahead addition. Besides non-associative prefix computation, we also propose parallel algorithms to generate Poisson random numbers. The design of Poisson generators are based on the theory of Poisson process and prefix computation. The time complexity of each generator is O([k/N]*T), where k is the number of uniform random numbers used during the generation of the required Poisson numbers, N is the number of processors, T is the time complexity of parallel prefix computation, and [x] represents the minimal integer >= x.

碩士
國立臺灣科技大學
電子工程系
87
Give n values x1, x2,…, xn and an associative binary operation , the prefix problem is to compute x1x2…xi, 1 ≧ i ≧ n. Because prefix computation has broad applications, many combinational circuits for solving the prefix problem, called prefix circuit, has been designed. The depth d(D(n)) and the size s(D(n)) of an n-input prefix circuit D(n) satisfy d(D(n)) + s(D(n)) ≧2n - 2; thus, the prefix circuit is depth-size optimal if d(D(n)) + s(D(n)) = 2n - 2. A prefix circuit with a smaller size requires less VLSI area, and one with smaller depth is faster. In addition, a node with smaller fan-out is faster and requires less VLSI area. In this thesis, we derive a size lower bound of parallel prefix circuits and construct two size optimal prefix circuits. We then use the two prefix circuits to construct three depth-size optimal prefix circuits M(n), M4(n), and MCL(n). M(n) and MCL(n) have unbounded fan-out and M4(n) has fan-out 4. MCL(n) has the smallest depth, but does not necessarily exist for all n ≧ 17. On the other hand, M(n) and M4(n) exist for all n ≧ 17. For most of the n values, the depth of M(n) is smaller than any other previously designed prefix circuit. Because the fan-out of M4(n) is smaller than that of M(n), the former needs less VLSI area; in addition, M4(n) may be faster than M(n) in spite of d(M4(n)) ≧ d(M(n)). Finally, we present a constant-time algorithm for finding depth-size optimal parallel prefix circuits with fan-out 2 and depths t either in the range 2lg n-1 < t < n-1 or 2lg n< t < n-1, depending on the value of n. 1.1. 平行前置電路的介紹 1 1.2. 相關研究 3 1.3. 論文組織 4 第二章、分層式前置電路與節點數最佳的前置電路 5 2.1. 無限扇出的P’(n)電路 5 2.2. 扇出為4的Q(n)電路 7 2.3. 節點數最佳的前置電路 8 第三章、一個具無限扇出的最佳前置電路 12 3.1. 節點數最佳的前置電路W(n) 12 3.2. 無限扇出的最佳前置電路M(n) 13 第四章、扇出為4的最佳前置電路M4(n) 17 第五章、另一個具無限扇出的最佳前置電路 21 5.1. 節點數最佳的前置電路CL(t, d) 21 5.2. 無限扇出的最佳前置電路MCL(n) 24 第六章、最佳前置電路的比較 26 第七章、用常數時間找出扇出為2的最佳前置電路 28 7.1. 扇出為2的最佳前置電路L(n) 28 7.2. 深度較大的最佳前置電路 30 第八章、結論與未來研究方向 32 8.1. 結論 32 8.2. 未來研究方向 32 附錄1、定理5.1的證明 33 附錄2、定理5.4的證明 47 參考資料 53

碩士
國立臺灣科技大學
資訊工程研究所
88
Give n values x1, x2,..., xn and an associative binary operation , the prefix operation is to compute x1 x2 ...xi, 1 ≦ i ≦ n. Because prefix computation has many applications, a large number of combinational circuits, called prefix circuits, have been designed to solve the prefix problem. The depth d(D(n)) and the size s(D(n)) of an n-input prefix circuit D(n) satisfy the inequality d(D(n)) + s(D(n)) ≧2n - 2; thus, the prefix circuit is depth-size optimal if d(D(n)) + s(D(n)) = 2n - 2. A prefix circuit with a smaller depth is usually faster, and one with a smaller size usually requires less VLSI area. Moreover, a node with a smaller fan-out is faster and smaller in VLSI implementation. The size, depth, and fan-out of a prefix circuit should be as small as possible. For prefix circuits with the same fan-out, a circuit with a smaller depth should be faster. In this thesis, we construct a depth-size optimal parallel prefix circuit H4(n) with fan-out 4; the depth of H4(n) is the smallest of all known prefix circuits with bounded fan-out. We also present a new layout scheme for prefix circuits; when it applies to a depth-size optimal prefix circuit, the layout area is the smallest.

博士
國立臺灣科技大學
資訊工程系
96
Given n inputs x1, x2,…, xn and an associative binary operator ♁, the prefix problem, or prefix computation, is to compute yi = x1 ♁ x2 ♁…♁ xi, for 1 ≤ i ≤ n. Prefix computation is used in various areas and is considered as a primitive operation. This thesis presents efficient algorithms for both multicomputer and combinational circuit models. Four families of computation-efficient parallel prefix algorithms for the multicomputer are given. The first two families generalize previous algorithms that use only half-duplex communications, and can improve the running time. The third and fourth families adopt collective communication operations to improve the communication time of the first two, respectively. The precondition of all the presented algorithms is also derived. The families of algorithms each provide the flexibility of choosing either less computation time or less communication time to achieve the minimal running time depending on the ratio of the time required by a communication step to the time required by a computation step. Parallel prefix circuits are parallel prefix algorithms on the combinational circuit model. The depth of a prefix circuit A, d(A), is a measure of its processing time; smaller depth implies faster computation. The size of a prefix circuit A, s(A), is the number of operation nodes in it; smaller size implies less power consumption, less VLSI area, and less cost. For any prefix circuit A of width m, which is the number of inputs, it has been shown that d(A) + s(A) ≥ 2m – 2; thus, A is depth-size optimal if d(A) + s(A) = 2m – 2. With the definition w(A), which is called waist of A, for any prefix circuit A of width m, it has been known that s(A) + w(A) ≥ 2m – 2. If s(A) + w(A) = 2m – 2 and w(A) = 1, then A is said to be waist-size optimal with waist 1 (WSO-1). A circuit with a smaller fan-out is in general faster and occupies less VLSI area. To be of practical use, the depth and fan-out of a prefix circuit should be small. This thesis presents prefix circuits with the smallest fan-out 2. In this thesis, a family of parallel prefix circuits is presented. These prefix circuits are WSO-1. They are not only building blocks for constructing fast depth-size optimal prefix circuits, but also themselves fast problem-size-independent prefix circuits. When the problem size is greater than the circuit width, a new prefix circuit may be well faster than any other prefix circuits of the same width, especially when the problem size is greater than or equal to twice the circuit width. The new prefix circuits are compared analytically with other representative ones circuits to show how fast they are. They have the minimum depth and are the fastest among all WSO-1 prefix circuits of the same width and fan-out. They are also better building blocks than other circuits for constructing fast depth-size optimal prefix circuits. A family of depth-size optimal, parallel prefix circuits with fan-out 2 is also presented. It is easier to construct and more amenable to automatic synthesis than two other families, all sharing the same minimum depth. The balanced structure of the new family is also a merit.

碩士
國立臺灣科技大學
電子工程技術研究所
86
Given n values v1, v2, ... , vn and an associative binary operation, denoted by o, the prefix problem is to compute the n prefixes v1 o v2 o ... o vi, 1 <= i <= n. We are interested in prefix computation on message-passing fully connected multicomputers. This thesis provides four parallel prefix algorithms in the multiport and multiport postal models. In the multiport model, Algorithm A uses n processors to solve the prefix problem. Algorithm B uses p(