Minimum mean running time function generation using read only memory /

Vita.

Read-only-memory-based quantum computation: Experimental explorations using nuclear magnetic resonance and future prospects

Read-only-memory-based (ROM-based) quantum computation (QC) is an alternative to oracle-based QC. It has the advantages of being less magical, and being more suited to implementing space-efficient computation (i.e., computation using the minimum number of writable qubits). Here we consider a number of small (one- and two-qubit) quantum algorithms illustrating different aspects of ROM-based QC. They are: (a) a one-qubit algorithm to solve the Deutsch problem; (b) a one-qubit binary multiplication algorithm; (c) a two-qubit controlled binary multiplication algorithm; and (d) a two-qubit ROM-based version of the Deutsch-Jozsa algorithm. For each algorithm we present experimental verification using nuclear magnetic resonance ensemble QC. The average fidelities for the implementation were in the ranges 0.9-0.97 for the one-qubit algorithms, and 0.84-0.94 for the two-qubit algorithms. We conclude with a discussion of future prospects for ROM-based quantum computation. We propose a four-qubit algorithm, using Grover's iterate, for solving a miniature real-world problem relating to the lengths of paths in a network.

Scaling In-Memory databases on multicores

Current computer systems have evolved from featuring only a single processing unit and limited RAM, in the order of kilobytes or few megabytes, to include several multicore processors, o↵ering in the order of several tens of concurrent execution contexts, and have main memory in the order of several tens to hundreds of gigabytes. This allows to keep all data of many applications in the main memory, leading to the development of inmemory databases. Compared to disk-backed databases, in-memory databases (IMDBs) are expected to provide better performance by incurring in less I/O overhead. In this dissertation, we present a scalability study of two general purpose IMDBs on multicore systems. The results show that current general purpose IMDBs do not scale on multicores, due to contention among threads running concurrent transactions. In this work, we explore di↵erent direction to overcome the scalability issues of IMDBs in multicores, while enforcing strong isolation semantics. First, we present a solution that requires no modification to either database systems or to the applications, called MacroDB. MacroDB replicates the database among several engines, using a master-slave replication scheme, where update transactions execute on the master, while read-only transactions execute on slaves. This reduces contention, allowing MacroDB to o↵er scalable performance under read-only workloads, while updateintensive workloads su↵er from performance loss, when compared to the standalone engine. Second, we delve into the database engine and identify the concurrency control mechanism used by the storage sub-component as a scalability bottleneck. We then propose a new locking scheme that allows the removal of such mechanisms from the storage sub-component. This modification o↵ers performance improvement under all workloads, when compared to the standalone engine, while scalability is limited to read-only workloads. Next we addressed the scalability limitations for update-intensive workloads, and propose the reduction of locking granularity from the table level to the attribute level. This further improved performance for intensive and moderate update workloads, at a slight cost for read-only workloads. Scalability is limited to intensive-read and read-only workloads. Finally, we investigate the impact applications have on the performance of database systems, by studying how operation order inside transactions influences the database performance. We then propose a Read before Write (RbW) interaction pattern, under which transaction perform all read operations before executing write operations. The RbW pattern allowed TPC-C to achieve scalable performance on our modified engine for all workloads. Additionally, the RbW pattern allowed our modified engine to achieve scalable performance on multicores, almost up to the total number of cores, while enforcing strong isolation.

ROM-based computation: Quantum versus classical

We introduce a model of computation based on read only memory (ROM), which allows us to compare the space-efficiency of reversible, error-free classical computation with reversible, error-free quantum computation. We show that a ROM-based quantum computer with one writable qubit is universal, whilst two writable bits are required for a universal classical ROM-based computer. We also comment on the time-efficiency advantages of quantum computation within this model.

Software transactional memory as a building block for parallel embedded realtime systems

The recent trends of chip architectures with higher number of heterogeneous cores, and non-uniform memory/non-coherent caches, brings renewed attention to the use of Software Transactional Memory (STM) as a fundamental building block for developing parallel applications. Nevertheless, although STM promises to ease concurrent and parallel software development, it relies on the possibility of aborting conflicting transactions to maintain data consistency, which impacts on the responsiveness and timing guarantees required by embedded real-time systems. In these systems, contention delays must be (efficiently) limited so that the response times of tasks executing transactions are upper-bounded and task sets can be feasibly scheduled. In this paper we assess the use of STM in the development of embedded real-time software, defending that the amount of contention can be reduced if read-only transactions access recent consistent data snapshots, progressing in a wait-free manner. We show how the required number of versions of a shared object can be calculated for a set of tasks. We also outline an algorithm to manage conflicts between update transactions that prevents starvation.

Efficient middleware for database replication

Dissertação de Mestrado em Engenharia Informática

Arithmetic-based binary-to-RNS converter modulo {2(n)+/- k} for jn-Bit dynamic range

In this brief, a read-only-memoryless structure for binary-to-residue number system (RNS) conversion modulo {2(n) +/- k} is proposed. This structure is based only on adders and constant multipliers. This brief is motivated by the existing {2(n) +/- k} binary-to-RNS converters, which are particular inefficient for larger values of n. The experimental results obtained for 4n and 8n bits of dynamic range suggest that the proposed conversion structures are able to significantly improve the forward conversion efficiency, with an AT metric improvement above 100%, regarding the related state of the art. Delay improvements of 2.17 times with only 5% area increase can be achieved if a proper selection of the {2(n) +/- k} moduli is performed.

Shelley’s editing process in the preface to Epipsychidion

Prefaces are often disregarded by readers who, more often than not, start without taking time to peruse them first. Sir Walter Scott knew this perfectly well, and he wrote about it, very wittily, in "A PostScript Which Should Have Been a Preface", the last chapter of his novel Waverley written in 1814: "most novel readers, as my own conscience reminds me, are apt to be guilty of the sin of omission respecting the same matter of prefaces". Scott refers to novel readers but poetry readers are also "guilty of the sin of omission", maybe even more so in so far as they may wish, understandably enough, to read only poetry and not a prose introduction. Many critics include prefaces in their analysis, but most of the time only as a means of interpreting the work they precede. Thus critics limit the role of prefaces simply to introductory materials and exclude any other potential interpretation. It is sometimes forgotten that the very presence or absence of a preface is already pregnant with meaning. [...]

Implementação de um protótipo de uma aplicação multimídia sobre a Ilha Rei George, Antártica

Esta dissertação aborda a implementação de um protótipo de aplicação multimídia referente à Ilha Rei George (61º 50’ S, 57º 30’ W e 62º 15’ S, 59º 00' W), Antártica. Nessa ilha o Brasil mantém sua única estação polar, onde realiza parte das pesquisas do Programa Antártico Brasileiro (PROANTAR). O presente trabalho visa reduzir a carência por materiais didáticos em língua portuguesa sobre as regiões polares e aborda aspectos gerais da biota, geografia física (geologia, climatologia e oceanografia) e geografia humana (história de ocupação, turismo, pesquisa e impactos gerados pela presença humana). O público alvo são pessoas com nível de instrução de ensino médio incompleto ou níveis mais avançados. O conteúdo é apresentado de forma a cativar a atenção do usuário, sem exageros estéticos. A fim de obter material para subsidiar o projeto, foram realizados registros por meio de fotografias, gravações em vídeo e entrevistas durante os trabalhos de campo na ilha, realizados no verão de 2004. Além dos registros em campo, são apresentados materiais didáticos tais como textos, ilustrações e animações em 3D. Parte do material gerado está disponível para utilização posterior em outros projetos O ambiente de desenvolvimento utilizado para a aplicação foi o Macromedia Director, para Apple Macintosh. O produto do projeto é um protótipo que pode ser distribuído em mídia removível, CD-ROM (Compact Disk Read Only Memory) ou DVD-ROM (Digital Versatile Disc Read Only Memory) e é encontrado como um encarte no final desta dissertação. A informação compilada e reunida na aplicação permite ao público acesso a dados atualizados sobre o ambiente antártico de forma simples, didática e interativa. O trabalho esclarece as relações entre a Antártica e o mundo, principalmente no que faz referência à ilha Rei George, buscando a valorização das regiões polares.

Práticas de formação continuada da EJA pelo olhar investigativo da formadora

Pós-graduação em Educação - IBRC

A recepção crítica de J.-K. Huysmans em periódicos no Brasil (1884 – 2013)

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Components of verbal working memory: Evidence from neuroimaging

We review research on the neural bases of verbal working memory, focusing on human neuroimaging studies. We first consider experiments that indicate that verbal working memory is composed of multiple components. One component involves the subvocal rehearsal of phonological information and is neurally implemented by left-hemisphere speech areas, including Broca’s area, the premotor area, and the supplementary motor area. Other components of verbal working memory may be devoted to pure storage and to executive processing of the contents of memory. These studies rest on a subtraction logic, in which two tasks are imaged, differing only in that one task presumably has an extra process, and the difference image is taken to reflect that process. We then review studies that show that the previous results can be obtained with experimental methods other than subtraction. We focus on the method of parametric variation, in which a parameter that presumably reflects a single process is varied. In the last section, we consider the distinction between working memory tasks that require only storage of information vs. those that require that the stored items be processed in some way. These experiments provide some support for the hypothesis that, when a task requires processing the contents of working memory, the dorsolateral prefrontal cortex is disproportionately activated.

A type system with usage aspects

Linear typing schemes can be used to guarantee non-interference and so the soundness of in-place update with respect to a functional semantics. But linear schemes are restrictive in practice, and more restrictive than necessary to guarantee soundness of in-place update. This limitation has prompted research into static analysis and more sophisticated typing disciplines to determine when in-place update may be safely used, or to combine linear and non-linear schemes. Here we contribute to this direction by defining a new typing scheme that better approximates the semantic property of soundness of in-place update for a functional semantics. We begin from the observation that some data are used only in a read-only context, after which it may be safely re-used before being destroyed. Formalising the in-place update interpretation in a machine model semantics allows us to refine this observation, motivating three usage aspects apparent from the semantics that are used to annotate function argument types. The aspects are (1) used destructively, (2), used read-only but shared with result, and (3) used read-only and not shared with the result. The main novelty is aspect (2), which allows a linear value to be safely read and even aliased with a result of a function without being consumed. This novelty makes our type system more expressive than previous systems for functional languages in the literature. The system remains simple and intuitive, but it enjoys a strong soundness property whose proof is non-trivial. Moreover, our analysis features principal types and feasible type reconstruction, as shown in M. Konen'y (In TYPES 2002 workshop, Nijmegen, Proceedings, Springer-Verlag, 2003).

Algorithms for efficient transaction management and consistent queries in client -server semantic object-oriented parallel databases

Large read-only or read-write transactions with a large read set and a small write set constitute an important class of transactions used in such applications as data mining, data warehousing, statistical applications, and report generators. Such transactions are best supported with optimistic concurrency, because locking of large amounts of data for extended periods of time is not an acceptable solution. The abort rate in regular optimistic concurrency algorithms increases exponentially with the size of the transaction. The algorithm proposed in this dissertation solves this problem by using a new transaction scheduling technique that allows a large transaction to commit safely with significantly greater probability that can exceed several orders of magnitude versus regular optimistic concurrency algorithms. A performance simulation study and a formal proof of serializability and external consistency of the proposed algorithm are also presented.^ This dissertation also proposes a new query optimization technique (lazy queries). Lazy Queries is an adaptive query execution scheme which optimizes itself as the query runs. Lazy queries can be used to find an intersection of sub-queries in a very efficient way, which does not require full execution of large sub-queries nor does it require any statistical knowledge about the data.^ An efficient optimistic concurrency control algorithm used in a massively parallel B-tree with variable-length keys is introduced. B-trees with variable-length keys can be effectively used in a variety of database types. In particular, we show how such a B-tree was used in our implementation of a semantic object-oriented DBMS. The concurrency control algorithm uses semantically safe optimistic virtual "locks" that achieve very fine granularity in conflict detection. This algorithm ensures serializability and external consistency by using logical clocks and backward validation of transactional queries. A formal proof of correctness of the proposed algorithm is also presented. ^