Automatically Evolving Rotation-invariant Texture Image Descriptors by Genetic Programming

In computer vision, training a model that performs classification effectively is highly dependent on the extracted features, and the number of training instances. Conventionally, feature detection and extraction are performed by a domain-expert who, in many cases, is expensive to employ and hard to find. Therefore, image descriptors have emerged to automate these tasks. However, designing an image descriptor still requires domain-expert intervention. Moreover, the majority of machine learning algorithms require a large number of training examples to perform well. However, labelled data is not always available or easy to acquire, and dealing with a large dataset can dramatically slow down the training process. In this paper, we propose a novel Genetic Programming based method that automatically synthesises a descriptor using only two training instances per class. The proposed method combines arithmetic operators to evolve a model that takes an image and generates a feature vector. The performance of the proposed method is assessed using six datasets for texture classification with different degrees of rotation, and is compared with seven domain-expert designed descriptors. The results show that the proposed method is robust to rotation, and has significantly outperformed, or achieved a comparable performance to, the baseline methods.

High-performance parallel systems for data-intensive computing

Thesis (Ph.D.)--University of Washington, 2016-08

From Kandinsky to Java (The Use of 20th Century Abstract Art in Learning Programming)

At the University of Worcester we are continually striving to find new approaches to the learning and teaching of programming, to improve the quality of learning and the student experience. Over the past three years we have used the contexts of robotics, computer games, and most recently a study of Abstract Art to this end. This paper discusses our motivation for using Abstract Art as a context, details our principles and methodology, and reports on an evaluation of the student experience. Our basic tenet is that one can view the works of artists such as Kandinsky, Klee and Malevich as Object-Oriented (OO) constructions. Discussion of these works can therefore be used to introduce OO principles, to explore the meaning of classes, methods and attributes and finally to synthesize new works of art through Java code. This research has been conducted during delivery of an ���Advanced OOP (Java)��� programming module at final-year Undergraduate level, and during a Masters��� OO-Programming (Java) module. This allows a comparative evaluation of novice and experienced programmers��� learning. In this paper, we identify several instructional factors which emerge from our approach, and reflect upon the associated pedagogy. A Catalogue of ArtApplets is provided at the associated web-site.

Database evolution on an orthogonal persistent programming system: A semi-transparent approach

In this paper the problem of the evolution of an object-oriented database in the context of orthogonal persistent programming systems is addressed. We have observed two characteristics in that type of systems that offer particular conditions to implement the evolution in a semi-transparent fashion. That transparency can further be enhanced with the obliviousness provided by the Aspect-Oriented Programming techniques. Was conceived a meta-model and developed a prototype to test the feasibility of our approach. The system allows programs, written to a schema, access semi-transparently to data in other versions of the schema.

Dynamic Workload Parallelization and System Calibration on Single-Chip Cloud Computer

Many-core systems are emerging from the need of more computational power and power efficiency. However there are many issues which still revolve around the many-core systems. These systems need specialized software before they can be fully utilized and the hardware itself may differ from the conventional computational systems. To gain efficiency from many-core system, programs need to be parallelized. In many-core systems the cores are small and less powerful than cores used in traditional computing, so running a conventional program is not an efficient option. Also in Network-on-Chip based processors the network might get congested and the cores might work at different speeds. In this thesis is, a dynamic load balancing method is proposed and tested on Intel 48-core Single-Chip Cloud Computer by parallelizing a fault simulator. The maximum speedup is difficult to obtain due to severe bottlenecks in the system. In order to exploit all the available parallelism of the Single-Chip Cloud Computer, a runtime approach capable of dynamically balancing the load during the fault simulation process is used. The proposed dynamic fault simulation approach on the Single-Chip Cloud Computer shows up to 45X speedup compared to a serial fault simulation approach. Many-core systems can draw enormous amounts of power, and if this power is not controlled properly, the system might get damaged. One way to manage power is to set power budget for the system. But if this power is drawn by just few cores of the many, these few cores get extremely hot and might get damaged. Due to increase in power density multiple thermal sensors are deployed on the chip area to provide realtime temperature feedback for thermal management techniques. Thermal sensor accuracy is extremely prone to intra-die process variation and aging phenomena. These factors lead to a situation where thermal sensor values drift from the nominal values. This necessitates efficient calibration techniques to be applied before the sensor values are used. In addition, in modern many-core systems cores have support for dynamic voltage and frequency scaling. Thermal sensors located on cores are sensitive to the core's current voltage level, meaning that dedicated calibration is needed for each voltage level. In this thesis a general-purpose software-based auto-calibration approach is also proposed for thermal sensors to calibrate thermal sensors on different range of voltages.

Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-��)-approximations for CLIQUE require LPs of size 2^{n��(��)}. This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

Proof Methods for Corecursive Programs

Recursion is a well-known and powerful programming technique, with a wide variety of applications. The dual technique of corecursion is less well-known, but is increasingly proving to be just as useful. This article is a tutorial on the four main methods for proving properties of corecursive programs: fixpoint induction, the approximation (or take) lemma, coinduction, and fusion.

Proof methods for structured corecursive programs

Corecursive programs produce values of greatest fixpoint types, in contrast to recursive programs, which consume values of least fixpoint types. There are a number of widely used methods for proving properties of corecursive programs, including fixpoint induction, the take lemma, and coinduction. However, these methods are all rather low level, in that they do not exploit the common structure that is often present in corecursive definitions. We argue for a more structured approach to proving properties of corecursive programs. In particular, we show that by writing corecursive programs using a simple operator that encapsulates a common pattern of corecursive definition, we can then use high-level algebraic properties of this operator to conduct proofs in a purely calculational style that avoids the use of inductive or coinductive methods.

Separate compilation of structured documents

This paper draws a parallel between document preparation and the traditional processes of compilation and link editing for computer programs. A block-based document model is described which allows for separate compilation of various portions of a document. These portions are brought together and merged by a linker program, called dlink, whose pilot implementation is based on ditroff and on its underlying intermediate code. In the light of experiences with dlink the requirements for a universal object-module language for documents are discussed. These requirements often resemble the characteristics of the intermediate codes used by programming-language compilers but with interesting extra constraints which arise from the way documents are executed .

Specification and Runtime Verification of Java Card Programs

COSTA, Umberto Souza da; MOREIRA, Anamaria Martins; MUSICANTE, Martin A. Specification and Runtime Verification of Java Card Programs. Electronic Notes in Theoretical Computer Science. [S.l:s.n], 2009.

Student attitudes to plagiarism and collusion within computer science

There is a widespread perception among staff in Computer Science that plagiarism is a major problem particularly in the form of collusion in programming exercises. While departments often make use of electronic detection measures, the time consumed prosecuting plagiarism offences remains a problem. As a result departments continue to seek ways to reduce the amount of plagiarism and collusion that occurs. This paper reports the findings of a questionnaire based study which attempted to assess the students' attitudes to the issues involved in the hope that such an understanding might result in practical measures for minimizing the problem. The study revealed that while students did understand the definition of plagiarism in its most extreme cases they were often confused about less clear-cut situations. Changes in the previous experience of incoming students meeting modules originally designed on the assumption that students already had some programming background and were equipped for self-directed study would also appear to be a contributory factor in the extent of collusion in programming exercises.

GPRM: a high performance programming framework for manycore processors

Processors with large numbers of cores are becoming commonplace. In order to utilise the available resources in such systems, the programming paradigm has to move towards increased parallelism. However, increased parallelism does not necessarily lead to better performance. Parallel programming models have to provide not only flexible ways of defining parallel tasks, but also efficient methods to manage the created tasks. Moreover, in a general-purpose system, applications residing in the system compete for the shared resources. Thread and task scheduling in such a multiprogrammed multithreaded environment is a significant challenge. In this thesis, we introduce a new task-based parallel reduction model, called the Glasgow Parallel Reduction Machine (GPRM). Our main objective is to provide high performance while maintaining ease of programming. GPRM supports native parallelism; it provides a modular way of expressing parallel tasks and the communication patterns between them. Compiling a GPRM program results in an Intermediate Representation (IR) containing useful information about tasks, their dependencies, as well as the initial mapping information. This compile-time information helps reduce the overhead of runtime task scheduling and is key to high performance. Generally speaking, the granularity and the number of tasks are major factors in achieving high performance. These factors are even more important in the case of GPRM, as it is highly dependent on tasks, rather than threads. We use three basic benchmarks to provide a detailed comparison of GPRM with Intel OpenMP, Cilk Plus, and Threading Building Blocks (TBB) on the Intel Xeon Phi, and with GNU OpenMP on the Tilera TILEPro64. GPRM shows superior performance in almost all cases, only by controlling the number of tasks. GPRM also provides a low-overhead mechanism, called ���Global Sharing���, which improves performance in multiprogramming situations. We use OpenMP, as the most popular model for shared-memory parallel programming as the main GPRM competitor for solving three well-known problems on both platforms: LU factorisation of Sparse Matrices, Image Convolution, and Linked List Processing. We focus on proposing solutions that best fit into the GPRM���s model of execution. GPRM outperforms OpenMP in all cases on the TILEPro64. On the Xeon Phi, our solution for the LU Factorisation results in notable performance improvement for sparse matrices with large numbers of small blocks. We investigate the overhead of GPRM���s task creation and distribution for very short computations using the Image Convolution benchmark. We show that this overhead can be mitigated by combining smaller tasks into larger ones. As a result, GPRM can outperform OpenMP for convolving large 2D matrices on the Xeon Phi. Finally, we demonstrate that our parallel worksharing construct provides an efficient solution for Linked List processing and performs better than OpenMP implementations on the Xeon Phi. The results are very promising, as they verify that our parallel programming framework for manycore processors is flexible and scalable, and can provide high performance without sacrificing productivity.

Visual programming in a heterogeneous multi-core environment

�� do conhecimento geral de que, hoje em dia, a tecnologia evolui rapidamente. S��o criadas novas arquitecturas para resolver determinadas limita����es ou problemas. Por vezes, essa evolu����o �� pac��fica e n��o requer necessidade de adapta����o e, por outras, essa evolu����o pode Implicar mudan��as. As linguagens de programa����o s��o, desde sempre, o principal elo de comunica����o entre o programador e o computador. Novas linguagens continuam a aparecer e outras est��o sempre em desenvolvimento para se adaptarem a novos conceitos e paradigmas. Isto requer um esfor��o extra para o programador, que tem de estar sempre atento a estas mudan��as. A Programa����o Visual pode ser uma solu����o para este problema. Exprimir fun����es como m��dulos que recebem determinado Input e retomam determinado output poder�� ajudar os programadores espalhados pelo mundo, atrav��s da possibilidade de lhes dar uma margem para se abstra��rem de pormenores de baixo n��vel relacionados com uma arquitectura espec��fica. Esta tese n��o s�� mostra como combinar as capacidades do CeII/B.E. (que tem uma arquitectura multi��processador heterog��nea) com o OpenDX (que tem um ambiente de programa����o visual), como tamb��m demonstra que tal pode ser feito sem grande perda de performance. ABSTRACT; lt is known that nowadays technology develops really fast. New architectures are created ln order to provide new solutions for different technology limitations and problems. Sometimes, this evolution is pacific and there is no need to adapt to new technologies, but things also may require a change every once ln a while. Programming languages have always been the communication bridge between the programmer and the computer. New ones keep coming and other ones keep improving ln order to adapt to new concepts and paradigms. This requires an extra-effort for the programmer, who always needs to be aware of these changes. Visual Programming may be a solution to this problem. Expressing functions as module boxes which receive determined Input and return determined output may help programmers across the world by giving them the possibility to abstract from specific low-level hardware issues. This thesis not only shows how the CeII/B.E. (which has a heterogeneous multi-core architecture) capabilities can be combined with OpenDX (which has a visual programming environment), but also demonstrates that lt can be done without losing much performance.

Fabrication and Pseudo-Analog Characteristics of Ta2O5 -Based ReRAM Cell

Memristori on yksi elektroniikan peruskomponenteista vastuksen, kondensaattorin ja kelan lis��ksi. Se on passiivinen komponentti, jonka teorian kehitti Leon Chua vuonna 1971. Kesti kuitenkin yli kolmekymment�� vuotta ennen kuin teoria pystyttiin yhdist��m����n kokeellisiin tuloksiin. Vuonna 2008 Hewlett Packard julkaisi artikkelin, jossa he v��ittiv��t valmistaneensa ensimm��isen toimivan memristorin. Memristori eli muistivastus on resistiivinen komponentti, jonka vastusarvoa pystyt����n muuttamaan. Nimens mukaisesti memristori kykenee my��s s��ilytt��m����n vastusarvonsa ilman jatkuvaa virtaa ja j��nnitett��. Tyypillisesti memristorilla on v��hint����n kaksi vastusarvoa, joista kumpikin pystyt����n valitsemaan sy��tt��m��ll�� komponentille j��nnitett�� tai virtaa. T��m��n vuoksi memristoreita kutsutaankin usein resistiivisiksi kytkimiksi. Resistiivisi�� kytkimi�� tutkitaan nyky����n paljon erityisesti niiden mahdollistaman muistiteknologian takia. Resistiivisist�� kytkimist�� rakennettua muistia kutsutaan ReRAM-muistiksi (lyhenne sanoista resistive random access memory). ReRAM-muisti on Flash-muistin tapaan haihtumaton muisti, jota voidaan s��hk��isesti ohjelmoida tai tyhjent����. Flash-muistia k��ytet����n t��ll�� hetkell�� esimerkiksi muistitikuissa. ReRAM-muisti mahdollistaa kuitenkin nopeamman ja v��h��virtaiseman toiminnan Flashiin verrattuna, joten se on tulevaisuudessa varteenotettava kilpailija markkinoilla. ReRAM-muisti mahdollistaa my��s useammin bitin tallentamisen yhteen muistisoluun bin����risen (���0��� tai ���1���) toiminnan sijaan. Tyypillisesti ReRAM-muistisolulla on kaksi rajoittavaa vastusarvoa, mutta n��iden kahden tilan v��lille pystyt����n mahdollisesti ohjelmoimaan useampia tiloja. Muistisoluja voidaan kutsua analogisiksi, jos tilojen m����r���� ei ole rajoitettu. Analogisilla muistisoluilla olisi mahdollista rakentaa tehokkaasti esimerkiksi neuroverkkoja. Neuroverkoilla pyrit����n mallintamaan aivojen toimintaa ja suorittamaan teht��vi��, jotka ovat tyypillisesti vaikeita perinteisille tietokoneohjelmille. Neuroverkkoja k��ytet����n esimerkiksi puheentunnistuksessa tai teko��lytoteutuksissa. T��ss�� diplomity��ss�� tarkastellaan Ta2O5 -perustuvan ReRAM-muistisolun analogista toimintaa pit��en mieless�� soveltuvuus neuroverkkoihin. ReRAM-muistisolun valmistus ja mittaustulokset k��yd����n l��pi. Muistisolun toiminta on harvoin t��ysin analogista, koska kahden rajoittavan vastusarvon v��lill�� on usein rajattu m����r�� tiloja. T��m��n vuoksi toimintaa kutsutaan pseudoanalogiseksi. Mittaustulokset osoittavat, ett�� yksitt��inen ReRAM-muistisolu kykenee bin����riseen toimintaan hyvin. Joiltain osin yksitt��inen solu kykenee tallentamaan useampia tiloja, mutta vastusarvoissa on per��kk��isten ohjelmointisyklien v��lill�� suurta vaihtelevuutta, joka hankaloittaa tulkintaa. Valmistettu ReRAM-muistisolu ei sellaisenaan kykene toimimaan pseudoanalogisena muistina, vaan se vaati rinnalleen virtaa rajoittavan komponentin. My��s valmistusprosessin kehitt��minen v��hent��isi yksitt��isen solun toiminnassa esiintyv���� varianssia, jolloin sen toiminta muistuttaisi enemm��n pseudoanalogista muistia.

Language-based Techniques for Practical and Trustworthy Secure Multi-party Computations

Secure Multi-party Computation (MPC) enables a set of parties to collaboratively compute, using cryptographic protocols, a function over their private data in a way that the participants do not see each other's data, they only see the final output. Typical MPC examples include statistical computations over joint private data, private set intersection, and auctions. While these applications are examples of monolithic MPC, richer MPC applications move between "normal" (i.e., per-party local) and "secure" (i.e., joint, multi-party secure) modes repeatedly, resulting overall in mixed-mode computations. For example, we might use MPC to implement the role of the dealer in a game of mental poker -- the game will be divided into rounds of local decision-making (e.g. bidding) and joint interaction (e.g. dealing). Mixed-mode computations are also used to improve performance over monolithic secure computations. Starting with the Fairplay project, several MPC frameworks have been proposed in the last decade to help programmers write MPC applications in a high-level language, while the toolchain manages the low-level details. However, these frameworks are either not expressive enough to allow writing mixed-mode applications or lack formal specification, and reasoning capabilities, thereby diminishing the parties' trust in such tools, and the programs written using them. Furthermore, none of the frameworks provides a verified toolchain to run the MPC programs, leaving the potential of security holes that can compromise the privacy of parties' data. This dissertation presents language-based techniques to make MPC more practical and trustworthy. First, it presents the design and implementation of a new MPC Domain Specific Language, called Wysteria, for writing rich mixed-mode MPC applications. Wysteria provides several benefits over previous languages, including a conceptual single thread of control, generic support for more than two parties, high-level abstractions for secret shares, and a fully formalized type system and operational semantics. Using Wysteria, we have implemented several MPC applications, including, for the first time, a card dealing application. The dissertation next presents Wys*, an embedding of Wysteria in F*, a full-featured verification oriented programming language. Wys* improves on Wysteria along three lines: (a) It enables programmers to formally verify the correctness and security properties of their programs. As far as we know, Wys* is the first language to provide verification capabilities for MPC programs. (b) It provides a partially verified toolchain to run MPC programs, and finally (c) It enables the MPC programs to use, with no extra effort, standard language constructs from the host language F*, thereby making it more usable and scalable. Finally, the dissertation develops static analyses that help optimize monolithic MPC programs into mixed-mode MPC programs, while providing similar privacy guarantees as the monolithic versions.