The two well-known approaches to designing combinatorial generation algorithms are the recursive approach and the iterative approach. In this thesis a third design approach using coroutines, introduced by Knuth and Ruskey, is explored further. An introduction to coroutines and their implementation in modern languages (in particular Python) is provided, and the coroutine-based approach is introduced using an example, and contrasted with the recursive and iterative approaches. The coroutine sum, coroutine product, and coroutine symmetric sum constructs are defined to create an algebra of coroutines, and used to give concise definitions of coroutine-based algorithms for generating ideals of chain and forest posets. Afterwards, new coroutine-based variations of several algorithms, including the Steinhaus-Johnson-Trotter algorithm for generating permutations in Gray order, the Varol-Rotem algorithm for generating linear extensions in Gray order, and the Pruesse-Ruskey algorithm for generating signed linear extensions of a poset in Gray order, are given. / Graduate / 0984 / saba@uvic.ca

Typescript (photocopy) / xii, 241 leaves : ill. ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / Thesis (Ph.D.)--University of Adelaide, Dept. of Computing Science, 1980

Thesis (Ph.D.) -- University of Adelaide, Dept. of Computing Science, 1980. / Typescript (photocopy).

Typescript (photocopy). / Digitized by Kansas Correctional Industries

Typescript (photocopy). / Digitized by Kansas Correctional Industries

[pt] Sistemas orientados a eventos estão se tornando cada vez mais presentes em diversos domínios de aplicação. Sistemas gráficos interativos e sistemas distribuídos são exemplos clássicos de cenários favoráveis ao emprego do paradigma de programação orientada a eventos. Atualmente, novos cenários estão surgindo, tais como os ambientes de programação para telefones celulares e, apesar dessa crescente presença em sistemas computacionais, o paradigma de orientação a eventos ainda apresenta uma série de desafios, tais como a elaboração de mecanismos eficientes para o despacho de eventos e o gerenciamento concorrente da execução desses tratadores, otimizando o uso dos recursos computacionais disponíveis. Este trabalho apresenta um modelo para o desenvolvimento de escalonadores de eventos em ambientes de programação orientados a eventos. É feito um estudo dos principais modelos de escalonamento colaborativo dos eventos, utilizando corrotinas em conjunto com outros padrões de projeto estudados. Defende-se um modelo onde o escalonador é responsável por encapsular a complexidade do gerenciamento de múltiplas linhas de execução colaborativas, procurando otimizar o uso de CPU durante chamadas de métodos bloqueantes. O uso de corrotinas permite o fácil gerenciamento dessas múltiplas linhas de execução, através da definição de mecanismos de abstração de controle, que permitem o encapsulamento do contexto de execução e a suspensão e retomada do processamento de forma transparente ao escalonador e às próprias linhas de execução. O fato de ser um modelo de concorrência colaborativa evita problemas com o controle de acessos concorrentes ao estado compartilhado pelas várias linhas de execução gerenciadas pelo escalonador. O modelo é aplicado em dois cenários distintos: uma ferramenta de programação para telefones celulares, que são inerentemente orientados a eventos de processamento assíncrono e apresentam pouco poder de processamento e fortes restrições no uso da memória disponível; e um middleware CORBA escrito em Lua, onde a comunicação entre os objetos distribuídos é toda baseada no modelo de chamada remota de métodos. / [en] Event oriented systems are becoming present on many domains of applications. Distributed systems and graphical interactive systems are classical examples of environments that adapt well to the concept of event oriented programming. There are also emerging scenarios like cellphone runtime environments. Despite the growing presence on the computational systems, some challenges still remain, like efficient method dispatch models and the management of concurrent processing of the event handlers. This work propose a model for an event scheduler using collaborative routines. We introduce a study on some mainstream scheduler models and propose a model where the scheduler holds the responsibility to encapsulate the complexity of managing multiple lines of execution, minimizing the CPU time wasted with blocking methods. The coroutine model allows the management of these multiple lines of execution using a general control abstraction, which allows seamless context switching during the multiple suspending and resuming of the routine. Also, without preemption, there is no overhead due to access control of the shared resources. The proposed is tested on two different scenarios: one programming framework designed to be run mobile phones, a fully asynchronous environment with low processing power and severe memory constraints; and a CORBA middleware written in lua, where the communication between distributed objects is based on the remote procedure call modell.

In today’s Internet, it is highly desirable to have fast and scalable software packet processing solutions for network applications that run on commodity hardware. The advent of cloud computing drives the continued rapid growth of Internet traffic. Moreover, the development of emerging networking techniques, such as Network Function Virtualization, significantly shapes the need for implementing the network functions in software. Finally, with the advancement of modern platforms as well as software frameworks for packet processing, network applications have potential to process 100+ Gbps network traffic on a single commodity server. Representative frameworks include the Click modular router, the RouteBricks scalable routing architecture, and BUFFALO, the software-based Ethernet switch. Beneath this general-purpose routing and switching functionality lie a broad set of network applications, many of which are handled with custom methods to provide cost-effectiveness and flexibility. This thesis considers two long-standing networking applications, IP lookup and distributed denial-of-service (DDoS) mitigation, and proposes efficient software-based methods drawing from this new perspective. In this thesis, we first introduce several optimization techniques to accelerate network applications by taking advantage of modern CPU features. Then, we explore the IP lookup problem to find the longest matching prefix of an IP address in a set of prefixes. An ideal IP lookup algorithm should achieve small constant IP lookup time, and on-chip memory usage. However, no prior IP lookup algorithm achieves both requirements at the same time. We propose SAIL, a splitting approach to IP lookup, and a suite of algorithms for IP lookup based on SAIL framework. We conducted extensive experiments to evaluate our algorithms, and experimental results show that our SAIL algorithms are much faster than well-known IP lookup algorithms. Next, we switch our focus to DDoS, an attempt to disrupt the legitimate traffic of a victim by sending a flood of Internet traffic from different sources. Our solution is Gatekeeper, the first open-source and deployable DDoS mitigation system. We present a series of optimization techniques, including use of modern platforms, group prefetching, coroutines, and hashing, to accelerate Gatekeeper. Experimental results show that these optimization techniques significantly improve its performance over alternative baseline solutions. / 2022-01-30T00:00:00Z

Ce mémoire vise à recenser les avantages et les inconvénients de l'utilisation du langage de programmation fonctionnel dynamique Scheme pour le développement de jeux vidéo. Pour ce faire, la méthode utilisée est d'abord basée sur une approche plus théorique. En effet, une étude des besoins au niveau de la programmation exprimés par ce type de développement, ainsi qu'une description détaillant les fonctionnalités du langage Scheme pertinentes au développement de jeux vidéo sont données afin de bien mettre en contexte le sujet. Par la suite, une approche pratique est utilisée en effectuant le développement de deux jeux vidéo de complexités croissantes: Space Invaders et Lode Runner. Le développement de ces jeux vidéo a mené à l'extension du langage Scheme par plusieurs langages spécifiques au domaine et bibliothèques, dont notamment un système de programmation orienté objets et un système de coroutines. L'expérience acquise par le développement de ces jeux est finalement comparée à celle d'autres développeurs de jeux vidéo de l'industrie qui ont utilisé Scheme pour la création de titres commerciaux. En résumé, l'utilisation de ce langage a permis d'atteindre un haut niveau d'abstraction favorisant la modularité des jeux développés sans affecter les performances de ces derniers. / This master's thesis aims at pinpointing the pros and cons of using the dynamic functionnal language Scheme for developing video games. The method used is first based on a theoretical approach. Indeed, the specific requirements for video game programming and a detailed description of relevant Scheme features are presented. Then, a practical approach is taken by presenting two video games developed using the Scheme language: Space Invaders and Lode Runner. Their development resulted in the creation of various domain-specific languages and libraries, such as an objec- oriented system and a coroutine system. Each of these are presented separately in their respective chapter. Finally, the experience achieved in this process is compared to the experience acquired by some video game companies that also used Scheme for the developpement of their titles. The use of Scheme allowed us to perform various high-level abstractions that improved the modularity of the video games developed, without affecting their performance.

Ce mémoire vise à recenser les avantages et les inconvénients de l'utilisation du langage de programmation fonctionnel dynamique Scheme pour le développement de jeux vidéo. Pour ce faire, la méthode utilisée est d'abord basée sur une approche plus théorique. En effet, une étude des besoins au niveau de la programmation exprimés par ce type de développement, ainsi qu'une description détaillant les fonctionnalités du langage Scheme pertinentes au développement de jeux vidéo sont données afin de bien mettre en contexte le sujet. Par la suite, une approche pratique est utilisée en effectuant le développement de deux jeux vidéo de complexités croissantes: Space Invaders et Lode Runner. Le développement de ces jeux vidéo a mené à l'extension du langage Scheme par plusieurs langages spécifiques au domaine et bibliothèques, dont notamment un système de programmation orienté objets et un système de coroutines. L'expérience acquise par le développement de ces jeux est finalement comparée à celle d'autres développeurs de jeux vidéo de l'industrie qui ont utilisé Scheme pour la création de titres commerciaux. En résumé, l'utilisation de ce langage a permis d'atteindre un haut niveau d'abstraction favorisant la modularité des jeux développés sans affecter les performances de ces derniers. / This master's thesis aims at pinpointing the pros and cons of using the dynamic functionnal language Scheme for developing video games. The method used is first based on a theoretical approach. Indeed, the specific requirements for video game programming and a detailed description of relevant Scheme features are presented. Then, a practical approach is taken by presenting two video games developed using the Scheme language: Space Invaders and Lode Runner. Their development resulted in the creation of various domain-specific languages and libraries, such as an objec- oriented system and a coroutine system. Each of these are presented separately in their respective chapter. Finally, the experience achieved in this process is compared to the experience acquired by some video game companies that also used Scheme for the developpement of their titles. The use of Scheme allowed us to perform various high-level abstractions that improved the modularity of the video games developed, without affecting their performance.

[pt] O objetivo deste trabalho é defender o resgate do conceito de co-rotinas como uma construção de controle poderosa e conveniente, que pode substituir tanto continuações de primeira classe como threads com um conceito único e mais simples. Para suprir a ausência de uma definição precisa e adequada para o conceito de co-rotinas, propomos um novo sistema de classificação, e introduzimos o conceito de co- rotinas completas, para o qual provemos uma definição formal, baseada em uma semântica operacional. Demonstramos a seguir a equivalência de poder expressivo entre co-rotinas completas simétricas e assimétricas e entre co-rotinas completas e continuações one-shot tradicionais e parciais, discutindo as vantagens de corotinas completas assimétricas em relação a co-rotinas simétricas e continuações de primeira classe. Finalmente, analizamos os benefícios e desvantagens associados aos diversos modelos de concorrência, justificando a adoção de modelos alternativos a multithreading e o oferecimento de co-rotinas como uma construção básica de concorrência, adequada à implementação desses modelos. / [en] The purpose of this work is to defend the revival of coroutines as a powerful and convenient control construct, which can replace both firstclass continuations and threads with a single and simpler concept. In order to provide an adequate and precise definition of the concept of coroutines, we propose a new classifying system, and introduce the concept of complete coroutines, for which we provide a formal definition based on an operational semantics. We then demostrate that complete symmetric coroutines and complete asymmetric coroutines have equivalent expressive power, as well as complete coroutines and one-shot traditional and partial continuations. We also discuss the advantages of using complete asymmetric coroutines instead of symmetric coroutines or first-class continuations. Finally, we analyse the benefits and problems associated with different concurrency models, and argue in favor of the replacement of multithreading with alternative concurrency models and the provision of coroutines as a basic concurrency construct, adequate for the implementation of these alternative models.