Systolic random number generation for genetic algorithms

A parallel hardware random number generator for use with a VLSI genetic algorithm processing device is proposed. The design uses an systolic array of mixed congruential random number generators. The generators are constantly reseeded with the outputs of the proceeding generators to avoid significant biasing of the randomness of the array which would result in longer times for the algorithm to converge to a solution. 1 Introduction In recent years there has been a growing interest in developing hardware genetic algorithm devices [1, 2, 3]. A genetic algorithm (GA) is a stochastic search and optimization technique which attempts to capture the power of natural selection by evolving a population of candidate solutions by a process of selection and reproduction [4]. In keeping with the evolutionary analogy, the solutions are called chromosomes with each chromosome containing a number of genes. Chromosomes are commonly simple binary strings, the bits being the genes.

A new organization for a perceptron-based branch predictor and its FPGA implementation

An unaltered rearrangement of the original computation of a neural based predictor at the algorithmic level is introduced as a new organization. Its FPGA implementation generates circuits that are 1.7 faster than a direct implementation of the original algorithm. This faster clock rate allows to implement predictors with longer history lengths using the nearly the same hardware budget.

Automatic artefact removal from event-related potentials via clustering

This paper outlines a method for automatic artefact removal from multichannel recordings of event-related potentials (ERPs). The proposed method is based on, firstly, separation of the ERP recordings into independent components using the method of temporal decorrelation source separation (TDSEP). Secondly, the novel lagged auto-mutual information clustering (LAMIC) algorithm is used to cluster the estimated components, together with ocular reference signals, into clusters corresponding to cerebral and non-cerebral activity. Thirdly, the components in the cluster which contains the ocular reference signals are discarded. The remaining components are then recombined to reconstruct the clean ERPs.

Uniformization of affine dependence programs for parallel embedded system design

This paper is concerned with the uniformization of a system of afine recurrence equations. This transformation is used in the design (or compilation) of highly parallel embedded systems (VLSI systolic arrays, signal processing filters, etc.). In this paper, we present and implement an automatic system to achieve uniformization of systems of afine recurrence equations. We unify the results from many earlier papers, develop some theoretical extensions, and then propose effective uniformization algorithms. Our results can be used in any high level synthesis tool based on polyhedral representation of nested loop computations.

Uniformization tool for systolic array designs

The paper is concerned with the uniformization of a system of affine recurrence equations. This transformation is used in the design (or compilation) of highly parallel embedded systems (VLSI systolic arrays, signal processing filters, etc.). We present and implement an automatic system to achieve uniformization of systems of affine recurrence equations. We unify the results from many earlier papers, develop some theoretical extensions, and then propose effective uniformization algorithms. Our results can be used in any high level synthesis tool based on polyhedral representation of nested loop computations.

Parallel pipelined array architectures for real-time histogram computation in consumer devices

The real-time parallel computation of histograms using an array of pipelined cells is proposed and prototyped in this paper with application to consumer imaging products. The array operates in two modes: histogram computation and histogram reading. The proposed parallel computation method does not use any memory blocks. The resulting histogram bins can be stored into an external memory block in a pipelined fashion for subsequent reading or streaming of the results. The array of cells can be tuned to accommodate the required data path width in a VLSI image processing engine as present in many imaging consumer devices. Synthesis of the architectures presented in this paper in FPGA are shown to compute the real-time histogram of images streamed at over 36 megapixels at 30 frames/s by processing in parallel 1, 2 or 4 pixels per clock cycle.

Arquiteturas multi-tarefas simultâneas : SEMPRE : arquitetura SMT com capacidade de execução e escalonamento de processos

O avanço tecnológico no projeto de microprocessadores, nos recentes anos, tem seguido duas tendências principais. A primeira tenta aumentar a freqüência do relógio dos mesmos usando componentes digitais e técnicas VLSI mais eficientes. A segunda tenta explorar paralelismo no nível de instrução através da reorganização dos seus componentes internos. Dentro desta segunda abordagem estão as arquiteturas multi-tarefas simultâneas, que são capazes de extrair o paralelismo existente entre e dentro de diferentes tarefas das aplicações, executando instruções de vários fluxos simultaneamente e maximizando assim a utilização do hardware. Apesar do alto custo da implementação em hardware, acredita-se no potencial destas arquiteturas para o futuro próximo, pois é previsto que em breve haverá a disponibilidade de bilhões de transistores para o desenvolvimento de circuitos integrados. Assim, a questão principal a ser encarada talvez seja: como prover instruções paralelas para uma arquitetura deste tipo? Sabe-se que a maioria das aplicações é seqüencial pois os problemas nem sempre possuem uma solução paralela e quando a solução existe os programadores nem sempre têm habilidade para ver a solução paralela. Pensando nestas questões a arquitetura SEMPRE foi projetada. Esta arquitetura executa múltiplos processos, ao invés de múltiplas tarefas, aproveitando assim o paralelismo existente entre diferentes aplicações. Este paralelismo é mais expressivo do que aquele que existe entre tarefas dentro de uma mesma aplicação devido a não existência de sincronismo ou comunicação entre elas. Portanto, a arquitetura SEMPRE aproveita a grande quantidade de processos existentes nas estações de trabalho compartilhadas e servidores de rede. Além disso, esta arquitetura provê suporte de hardware para o escalonamento de processos e instruções especiais para o sistema operacional gerenciar processos com mínimo esforço. Assim, os tempos perdidos com o escalonamento de processos e as trocas de contextos são insignificantes nesta arquitetura, provendo ainda maior desempenho durante a execução das aplicações. Outra característica inovadora desta arquitetura é a existência de um mecanismo de prébusca de processos que, trabalhando em cooperação com o escalonamento de processos, permite reduzir faltas na cache de instruções. Também, devido a essa rápida troca de contexto, a arquitetura permite a definição de uma fatia de tempo (fatia de tempo) menor do que aquela praticada pelo sistema operacional, provendo maior dinâmica na execução das aplicações. A arquitetura SEMPRE foi analisada e avaliada usando modelagem analítica e simulação dirigida por execução de programas do SPEC95. A modelagem mostrou que o escalonamento por hardware reduz os efeitos colaterais causados pela presença de processos na cache de instruções e a simulação comprovou que as diferentes características desta arquitetura podem, juntas, prover ganho de desempenho razoável sobre outras arquiteturas multi-tarefas simultâneas equivalentes, com um pequeno acréscimo de hardware, melhor aproveitando as fatias de tempo atribuídas aos processos.

Uma Técnica de depuração e teste de circuitos integrados usando um microscópio eletrônico

O trabalho tem por objetivo mostrar uma técnica de depuração de circuitos integrados VLSI, utilizando um microscópio eletrônico de varredura (MEV) aliado ao fenômeno de contraste por tensão. São abordadas a descrição da ferramenta, técnicas de observação e depuração dos circuitos, bem como, são sugeridas estratégias de concepção visando facilitar a depuração dos circuitos. Embora tenham sido utilizados circuitos NMOS para realizar as experiências, a técnica é aplicável a circuitos MOS em geral. Resultados experimentais, utilizando circuitos projetados no PGCC, são apresentados.

Mixed-signal analog-digital circuits design on the pre-diffused digital array using trapezoidal association of transistors

The mixed-signal and analog design on a pre-diffused array is a challenging task, given that the digital array is a linear matrix arrangement of minimum-length transistors. To surmount this drawback a specific discipline for designing analog circuits over such array is required. An important novel technique proposed is the use of TAT (Trapezoidal Associations of Transistors) composite transistors on the semi-custom Sea-Of-Transistors (SOT) array. The analysis and advantages of TAT arrangement are extensively analyzed and demonstrated, with simulation and measurement comparisons to equivalent single transistors. Basic analog cells were also designed as well in full-custom and TAT versions in 1.0mm and 0.5mm digital CMOS technologies. Most of the circuits were prototyped in full-custom and TAT-based on pre-diffused SOT arrays. An innovative demonstration of the TAT technique is shown with the design and implementation of a mixed-signal analog system, i. e., a fully differential 2nd order Sigma-Delta Analog-to-Digital (A/D) modulator, fabricated in both full-custom and SOT array methodologies in 0.5mm CMOS technology from MOSIS foundry. Three test-chips were designed and fabricated in 0.5mm. Two of them are IC chips containing the full-custom and SOT array versions of a 2nd-Order Sigma-Delta A/D modulator. The third IC contains a transistors-structure (TAT and single) and analog cells placed side-by-side, block components (Comparator and Folded-cascode OTA) of the Sigma-Delta modulator.

Uma interface para o aumento da faixa de freqüências de operação de FPAAS

O crescente avanço nas mais diversas áreas da eletrônica, desde instrumentação em baixa freqüência até telecomunicações operando em freqüências muito elevadas, e a necessidade de soluções baratas em curto espaço de tempo que acompanhem a demanda de mercado, torna a procura por circuitos programáveis, tanto digitais como analógicos, um ponto comum em diversas pesquisas. Os dispositivos digitais programáveis, que têm como grande representante os Field Programmable Gate Arrays (FPGAs), vêm apresentando um elevado e contínuo crescimento em termos de complexidade, desempenho e número de transistores integrados, já há várias décadas. O desenvolvimento de dispositivos analógicos programáveis (Field Programmable Analog Arrays – FPAAs), entretanto, esbarra em dois pontos fundamentais que tornam sua evolução um tanto latente: a estreita largura de banda alcançada, conseqüência da necessidade de um grande número de chaves de programação e reconfiguração, e a elevada área consumida por componentes analógicos como resistores e capacitores, quando integrados em processos VLSI Este trabalho apresenta uma proposta para aumentar a faixa de freqüências das aplicações passíveis de serem utilizadas tanto em FPAAs comerciais quanto em outros FPAAs, através da utilização de uma interface de translação e seleção de sinais, mantendo características de programabilidade do FPAA em questão, sem aumentar em muito sua potência consumida. A proposta, a simulação e a implementação da interface são apresentadas ao longo desta dissertação. Resultados de simulação e resultados práticos obtidos comprovam a eficácia da proposta.

Mecanismos de reconfiguração dinâmica aplicados ao projeto de um processador de imagens reconfigurável

As modernas aplicações em diversas áreas como multimídia e telecomunicações exigem arquiteturas que ofereçam altas taxas de processamento. Entretanto, os padrões e algoritmos mudam com incrível rapidez o que gera a necessidade de que esses sistemas digitais tenham também por característica uma grande flexibilidade. Dentro desse contexto, tem-se as arquiteturas reconfiguráveis em geral e, mais recentemente, os sistemas reconfiguráveis em um único chip como soluções adequadas que podem oferecer desempenho, sendo, ao mesmo tempo, adaptáveis a novos problemas e a classes mais amplas de algoritmos dentro de um dado escopo de aplicação. Este trabalho apresenta o estado-da-arte em relação a arquiteturas reconfiguráveis nos meios acadêmcio e industrial e descreve todas as etapas de desenvolvimento do processador de imagens reconfigurável DRIP (Dynamically Reconfigurable Image Processor), desde suas origens como um processador estático até sua última versão reconfigurável em tempo de execução. O DRIP possui um pipeline composto por 81 processadores elementares. Esses processadores constituem a chave do processo de reconfiguração e possuem a capacidade de computar um grande número de algoritmos de processamento de imagens, mais específicamente dentro do domínio da filtragem digital de imagens. Durante o projeto, foram desenvolvidos uma série de modelos em linguagem de descrição de hardware da arquitetura e também ferramentas de software para auxiliar nos processos de implementação de novos algorimos, geração automática de modelos VHDL e validação das implementações. O desenvolvimento de mecanismos com o objetivo de incluir a possibilidade de reconfiguração dinâmica, naturalmente, introduz overheads na arquitetura. Contudo, o processo de reconfiguração do DRIP-RTR é da ordem de milhões de vezes mais rápido do que na versão estaticamente reconfigurável implementada em FPGAs Altera. Finalizando este trabalho, é apresentado o projeto lógico e elétrico do processador elementar do DRIP, visando uma futura implementação do sistema diretamente como um circuito VLSI.