Toward a Scalable Working Set Size Estimation Method and Its Application for Chip Multiprocessors

It is essential to accurately estimate the working set size (WSS) of an application for various optimizations such as to partition cache among virtual machines or reduce leakage power dissipated in an over-allocated cache by switching it OFF. However, the state-of-the-art heuristics such as average memory access latency (AMAL) or cache miss ratio (CMR) are poorly correlated to the WSS of an application due to 1) over-sized caches and 2) their dispersed nature. Past studies focus on estimating WSS of an application executing on a uniprocessor platform. Estimating the same for a chip multiprocessor (CMP) with a large dispersed cache is challenging due to the presence of concurrently executing threads/processes. Hence, we propose a scalable, highly accurate method to estimate WSS of an application. We call this method ``tagged WSS (TWSS)'' estimation method. We demonstrate the use of TWSS to switch-OFF the over-allocated cache ways in Static and Dynamic NonUniform Cache Architectures (SNUCA, DNUCA) on a tiled CMP. In our implementation of adaptable way SNUCA and DNUCA caches, decision of altering associativity is taken by each L2 controller. Hence, this approach scales better with the number of cores present on a CMP. It gives overall (geometric mean) 26% and 19% higher energy-delay product savings compared to AMAL and CMR heuristics on SNUCA, respectively.

Energy-efficient, delay-constrained, QoS-aware broadcast for cooperative wireless sensor networks

The problem of delay-constrained, energy-efficient broadcast in cooperative wireless networks is NP-complete. While centralised setting allows some heuristic solutions, designing heuristics in distributed implementation poses significant challenges. This is more so in wireless sensor networks (WSNs) where nodes are deployed randomly and topology changes dynamically due to node failure/join and environment conditions. This paper demonstrates that careful design of network infrastructure can achieve guaranteed delay bounds and energy-efficiency, and even meet quality of service requirements during broadcast. The paper makes three prime contributions. First, we present an optimal lower bound on energy consumption for broadcast that is tighter than what has been previously proposed. Next, iSteiner, a lightweight, distributed and deterministic algorithm for creation of network infrastructure is discussed. iPercolate is the algorithm that exploits this structure to cooperatively broadcast information with guaranteed delivery and delay bounds, while allowing real-time traffic to pass undisturbed.

PLAStiCC: Predictive Look-Ahead Scheduling for Continuous dataflows on Clouds

Scalable stream processing and continuous dataflow systems are gaining traction with the rise of big data due to the need for processing high velocity data in near real time. Unlike batch processing systems such as MapReduce and workflows, static scheduling strategies fall short for continuous dataflows due to the variations in the input data rates and the need for sustained throughput. The elastic resource provisioning of cloud infrastructure is valuable to meet the changing resource needs of such continuous applications. However, multi-tenant cloud resources introduce yet another dimension of performance variability that impacts the application's throughput. In this paper we propose PLAStiCC, an adaptive scheduling algorithm that balances resource cost and application throughput using a prediction-based lookahead approach. It not only addresses variations in the input data rates but also the underlying cloud infrastructure. In addition, we also propose several simpler static scheduling heuristics that operate in the absence of accurate performance prediction model. These static and adaptive heuristics are evaluated through extensive simulations using performance traces obtained from Amazon AWS IaaS public cloud. Our results show an improvement of up to 20% in the overall profit as compared to the reactive adaptation algorithm.

SYNTHESIS OF CONCEPTUAL DESIGNS FOR SENSORS USING SAPPHIRE-LITE

The demand for variety of products and the shorter time to market is encouraging designers to adopt computer aided concept generation techniques. One such technique is being explored here. The present work makes an attempt towards synthesis of concepts for sensors using physical laws and effects as building blocks. A database of building blocks based upon the SAPPhIRE-lite model of causality is maintained. It uses composition to explore the solution space. The algorithm has been implemented in a web based tool. The tool generates two types of sensor designs: direct sensing designs and feedback sensing designs. According to the literature, synthesis using building blocks often lead to vague solutions principles. The current work tries to avoid uninteresting solutions by using some heuristics. A particularly novel outcome of the work described here is the generation of feedback based solutions, something not generated automatically before. A number of patent violations were observed with the set of generated concepts; thus emphasizing some amount of novelty in the designs.

SMO: An Integrated Approach to Intra-array and Inter-array Storage Optimization

The polyhedral model provides an expressive intermediate representation that is convenient for the analysis and subsequent transformation of affine loop nests. Several heuristics exist for achieving complex program transformations in this model. However, there is also considerable scope to utilize this model to tackle the problem of automatic memory footprint optimization. In this paper, we present a new automatic storage optimization technique which can be used to achieve both intra-array as well as inter-array storage reuse with a pre-determined schedule for the computation. Our approach works by finding statement-wise storage partitioning hyper planes that partition a unified global array space so that values with overlapping live ranges are not mapped to the same partition. Our heuristic is driven by a fourfold objective function which not only minimizes the dimensionality and storage requirements of arrays required for each high-level statement, but also maximizes inter statement storage reuse. The storage mappings obtained using our heuristic can be asymptotically better than those obtained by any existing technique. We implement our technique and demonstrate its practical impact by evaluating its effectiveness on several benchmarks chosen from the domains of image processing, stencil computations, and high-performance computing.

Design for all: designing for the motion-impaired user

Designing for all requires the adaptation and modification of current design best practices to encompass a broader range of user capabilities. This is particularly the case in the design of the human-product interface. Product interfaces exist everywhere and when designing them, there is a very strong temptation to jump to prescribing a solution with only a cursory attempt to understand the nature of the problem. This is particularly the case when attempting to adapt existing designs, optimised for able-bodied users, for use by disabled users. However, such approaches have led to numerous products that are neither usable nor commercially successful. In order to develop a successful design approach it is necessary consider the fundamental structure of the design process being applied. A three stage design process development strategy which includes problem definition, solution development and solution evaluation, should be adopted. This paper describes the development of a new design approach based on the application of usability heuristics to the design of interfaces. This is illustrated by reference to a particular case study of the re-design of a computer interface for controlling an assistive device.

Selective data gathering in community sensor networks

Smartphones and other powerful sensor-equipped consumer devices make it possible to sense the physical world at an unprecedented scale. Nearly 2 million Android and iOS devices are activated every day, each carrying numerous sensors and a high-speed internet connection. Whereas traditional sensor networks have typically deployed a fixed number of devices to sense a particular phenomena, community networks can grow as additional participants choose to install apps and join the network. In principle, this allows networks of thousands or millions of sensors to be created quickly and at low cost. However, making reliable inferences about the world using so many community sensors involves several challenges, including scalability, data quality, mobility, and user privacy.

This thesis focuses on how learning at both the sensor- and network-level can provide scalable techniques for data collection and event detection. First, this thesis considers the abstract problem of distributed algorithms for data collection, and proposes a distributed, online approach to selecting which set of sensors should be queried. In addition to providing theoretical guarantees for submodular objective functions, the approach is also compatible with local rules or heuristics for detecting and transmitting potentially valuable observations. Next, the thesis presents a decentralized algorithm for spatial event detection, and describes its use detecting strong earthquakes within the Caltech Community Seismic Network. Despite the fact that strong earthquakes are rare and complex events, and that community sensors can be very noisy, our decentralized anomaly detection approach obtains theoretical guarantees for event detection performance while simultaneously limiting the rate of false alarms.

Incremental Control Synthesis for Robotics in the Presence of Temporal Logic Specifications

This thesis presents methods for incrementally constructing controllers in the presence of uncertainty and nonlinear dynamics. The basic setting is motion planning subject to temporal logic specifications. Broadly, two categories of problems are treated. The first is reactive formal synthesis when so-called discrete abstractions are available. The fragment of linear-time temporal logic (LTL) known as GR(1) is used to express assumptions about an adversarial environment and requirements of the controller. Two problems of changes to a specification are posed that concern the two major aspects of GR(1): safety and liveness. Algorithms providing incremental updates to strategies are presented as solutions. In support of these, an annotation of strategies is developed that facilitates repeated modifications. A variety of properties are proven about it, including necessity of existence and sufficiency for a strategy to be winning. The second category of problems considered is non-reactive (open-loop) synthesis in the absence of a discrete abstraction. Instead, the presented stochastic optimization methods directly construct a control input sequence that achieves low cost and satisfies a LTL formula. Several relaxations are considered as heuristics to address the rarity of sampling trajectories that satisfy an LTL formula and demonstrated to improve convergence rates for Dubins car and single-integrators subject to a recurrence task.

Instances of combinatorial optimization problems: complexity and generation

138 p.

Proposição e análise de modelos híbridos para o problema de escalonamento de produção em oficina de máquinas

Nas últimas décadas, o problema de escalonamento da produção em oficina de máquinas, na literatura referido como JSSP (do inglês Job Shop Scheduling Problem), tem recebido grande destaque por parte de pesquisadores do mundo inteiro. Uma das razões que justificam tamanho interesse está em sua alta complexidade. O JSSP é um problema de análise combinatória classificado como NP-Difícil e, apesar de existir uma grande variedade de métodos e heurísticas que são capazes de resolvê-lo, ainda não existe hoje nenhum método ou heurística capaz de encontrar soluções ótimas para todos os problemas testes apresentados na literatura. A outra razão basea-se no fato de que esse problema encontra-se presente no diaa- dia das indústrias de transformação de vários segmento e, uma vez que a otimização do escalonamento pode gerar uma redução significativa no tempo de produção e, consequentemente, um melhor aproveitamento dos recursos de produção, ele pode gerar um forte impacto no lucro dessas indústrias, principalmente nos casos em que o setor de produção é responsável por grande parte dos seus custos totais. Entre as heurísticas que podem ser aplicadas à solução deste problema, o Busca Tabu e o Multidão de Partículas apresentam uma boa performance para a maioria dos problemas testes encontrados na literatura. Geralmente, a heurística Busca Tabu apresenta uma boa e rápida convergência para pontos ótimos ou subótimos, contudo esta convergência é frequentemente interrompida por processos cíclicos e a performance do método depende fortemente da solução inicial e do ajuste de seus parâmetros. A heurística Multidão de Partículas tende a convergir para pontos ótimos, ao custo de um grande esforço computacional, sendo que sua performance também apresenta uma grande sensibilidade ao ajuste de seus parâmetros. Como as diferentes heurísticas aplicadas ao problema apresentam pontos positivos e negativos, atualmente alguns pesquisadores começam a concentrar seus esforços na hibridização das heurísticas existentes no intuito de gerar novas heurísticas híbridas que reúnam as qualidades de suas heurísticas de base, buscando desta forma diminuir ou mesmo eliminar seus aspectos negativos. Neste trabalho, em um primeiro momento, são apresentados três modelos de hibridização baseados no esquema geral das Heurísticas de Busca Local, os quais são testados com as heurísticas Busca Tabu e Multidão de Partículas. Posteriormente é apresentada uma adaptação do método Colisão de Partículas, originalmente desenvolvido para problemas contínuos, onde o método Busca Tabu é utilizado como operador de exploração local e operadores de mutação são utilizados para perturbação da solução. Como resultado, este trabalho mostra que, no caso dos modelos híbridos, a natureza complementar e diferente dos métodos Busca Tabu e Multidão de Partículas, na forma como são aqui apresentados, da origem à algoritmos robustos capazes de gerar solução ótimas ou muito boas e muito menos sensíveis ao ajuste dos parâmetros de cada um dos métodos de origem. No caso do método Colisão de Partículas, o novo algorítimo é capaz de atenuar a sensibilidade ao ajuste dos parâmetros e de evitar os processos cíclicos do método Busca Tabu, produzindo assim melhores resultados.

Metaheurística para o Problema de Planejamento de Redes de Transmissão de Energia Elétrica com Redimensionamento

Com o passar do tempo, a demanda elétrica de diversas áreas varia tornando necessária a construção de novos geradores elétricos e a expansão da rede de transmissão de energia elétrica. Nesta dissertação, focamos no problema de expansão da rede de transmissão, assumindo que novos geradores estão construídos para suprir as novas demandas. Essa expansão exige altos investimentos que precisam ser cuidadosamente planejados. O problema pode ser modelado como um problema de otimização não linear inteira mista e pertence à classe dos problemas NP-difíceis. Desta forma, uma abordagem heurística pode ser adequada para a sua solução pois pode vir a fornecer boas soluções em tempo computacional aceitável. Esta dissertação se propõe a apresentar um estudo do problema de planejamento da expansão de redes de transmissão de energia elétrica estático e multiestágio. Mostramos o que já existe na literatura para o que é chamado de problema sem redimensionamento e as inovações feitas por nós para o problema com redimensionamento. Quanto aos métodos de solução, utilizamos a metaheurística GRASP para o problema estático e combinamos o GRASP com o procedimento Backward-Forward quando falamos em problema multiestágio. Nesta dissertação comparamos os resultados computacionais obtidos com resultados encontrados na literatura.

A legitimação jurídico-moral da regulação estatal à luz da premissa liberal republicana: autonomia privada, igualdade e autonomia pública. Estudo de caso sobre as regulações paternalistas

A presente tese tem por objetivo principal estudar a legitimação jurídico-moral da regulação estatal. Trata-se de tema de grande relevância e extrema atualidade em decorrência de dois fatores. Por um lado, desde o fenômeno da virada kantiana e da retomada da preocupação com o estabelecimento de uma teoria da justiça, tornou-se necessária a análise de justificação jurídico-moral de toda e qualquer instituição político-jurídica positivada. Por outro lado, entre as inúmeras instituições político-jurídicas positivadas, cresce cada vez mais a utilização das medidas jurídicas regulatórias, através das quais o Poder Público direciona ou controla a conduta dos agentes com o intuito de atingir determinada finalidade. Instituto econômico que é, ao interferir na alocação de riquezas, bens e serviços no mercado, a regulação estatal há tempos já vem sendo objeto de análise em uma perspectiva de legitimação econômica. Tradicionalmente, ainda dentro do paradigma da racionalidade, os economistas sempre apontaram as falhas de mercado como as razões a justificar as regulações estatais em um viés econômico. Mais recentemente, por sua vez, os adeptos da economia comportamental, rompendo ou relativizando as lições da Rational Choice Theory, têm apontado também as ações irracionais em heurística como razões a justificar as regulações estatais em um viés econômico. Ocorre, entretanto, que a regulação estatal é um instituto interdisciplinar. Ao direcionar ou controlar a conduta dos indivíduos, limitando ou implementando direitos e liberdades, a regulação constitui instituto simultaneamente jurídico e moral. A presente tese, portanto, buscará apresentar as razões a servir de justificação para a regulação estatal em uma perspectiva jurídico-moral. Neste ponto, adotar-se-á como paradigma de aferição de legitimação jurídico-moral das instituições político-jurídicas positivadas (entre as quais as regulações estatais) um liberalismo-republicano, consistente na compatibilização do liberalismo-igualitário com um republicanismo moderado. Desta forma, o estudo buscará defender a possibilidade de a legitimação jurídico-moral das diversas regulações estatais encontrar fundamento em um ou alguns de três valores jurídico-morais: a autonomia individual privada, as condições igualitárias e a autonomia pública. No que diz respeito à implementação da autonomia individual privada e das condições igualitárias, primeiramente, a tese defenderá a possibilidade de ser realizada uma nova leitura jurídico-moral dos institutos econômicos das falhas de mercado e das ações irracionais em heurística. Neste sentido, o conceito de falhas de mercado e o conceito de ações irracionais em heurística, em uma leitura jurídico-moral como razões a justificar a legitimação das regulações estatais, devem ser entendidos como situações em que o atuar livre dos agentes no mercado viole ou deixe de implementar os valores jurídico-morais fundamentais da autonomia individual privada e das condições igualitárias. Ainda no que diz respeito às influências liberal-igualitárias, a tese sustentará que, mesmo na inexistência de falhas de mercado ou de ações irracionais em heurística, será possível o estabelecimento de regulações estatais que encontrem justificação no valor jurídico-moral fundamental da igualdade, desde que tais regulações estejam destinadas a implementar as condições igualitárias mínimas necessárias à manutenção da própria autonomia individual privada e da dignidade humana. Por outro lado, no que diz respeito às influências republicanas, será exposto que as regulações estatais podem encontrar legitimação jurídico-moral também no valor jurídico-moral fundamental da autonomia pública. A saber, as regulações podem se encontrar legitimadas jurídico-moralmente quando da implementação dos projetos e políticas deliberados pelos cidadãos e pela sociedade no exercício da soberania popular, desde que tais projetos coletivos não violem os requisitos mínimos de dignidade humana dos indivíduos. A tese defenderá que os princípios da proporcionalidade e da igualdade podem exercer um papel de destaque na análise de legitimação jurídico-moral das regulações estatais. O princípio da proporcionalidade, neste ponto, será útil instrumental metodológico na aferição de legitimação jurídico-moral de uma medida regulatória em uma perspectiva interna, quando da aferição da relação estabelecida entre os meios e os fins da regulação. O princípio da igualdade, por sua vez, será útil instrumental metodológico na aferição de legitimação jurídico-moral de uma medida regulatória em uma perspectiva comparativa entre as diversas medidas regulatórias existentes. Por fim, uma vez enfrentados os pontos mais sensíveis pertinentes à justificação de toda e qualquer medida regulatória bem como estabelecida uma teoria geral acerca da legitimação jurídico-moral da regulação estatal, a presente tese realizará um estudo de caso acerca da legitimação jurídico-moral especificamente das regulações que utilizam argumentos de natureza paternalista. Trata-se de regulações que, ao direcionar a conduta de agentes com o intuito de zelar por bens, direitos e interesses destes próprios indivíduos cuja liberdade é restringida, apresentam-se extremamente controversas. Será exposto que, desde a clássica obra On Liberty de JONH STUART MILL, o paternalismo jurídico vem sendo tradicionalmente associado a uma conotação pejorativa de violação aos valores jurídico-morais fundamentais. A tese, porém, adotará posição segundo a qual as regulações paternalistas podem eventualmente encontrar legitimação jurídico-moral na promoção ou proteção dos valores jurídico-morais fundamentais da autonomia individual privada e da igualdade. Além disto, defenderá o estudo que os institutos econômicos das falhas de mercado da assimetria de informações e dos problemas de coordenação bem como os institutos econômicos das ações irracionais em heurística, adotados na nova leitura jurídico-moral proposta, servirão de instrumental útil na identificação das situações em que tais regulações paternalistas se encontram legitimadas jurídico-moralmente diante da premissa liberal-republicana.

Roteamento e alocação de comprimento de onda em redes WDM segundo algoritmo baseado em regras da natureza.

O surgimento de novos serviços de telecomunicações tem provocado um enorme aumento no tráfego de dados nas redes de transmissão. Para atender a essa demanda crescente, novas tecnologias foram desenvolvidas e implementadas ao longo dos anos, sendo que um dos principais avanços está na área de transmissão óptica, devido à grande capacidade de transporte de informação da fibra óptica. A tecnologia que melhor explora a capacidade desse meio de transmissão atualmente é a multiplexação por divisão de comprimento de onda ou Wavelength Division Multiplexing (WDM) que permite a transmissão de diversos sinais utilizando apenas uma fibra óptica. Redes ópticas WDM se tornaram muito complexas, com enorme capacidade de transmissão de informação (terabits por segundo), para atender à explosão de necessidade por largura de banda. Nesse contexto, é de extrema importância que os recursos dessas redes sejam utilizados de forma inteligente e otimizada. Um dos maiores desafios em uma rede óptica é a escolha de uma rota e a seleção de um comprimento de onda disponível na rede para atender uma solicitação de conexão utilizando o menor número de recursos possível. Esse problema é bastante complexo e ficou conhecido como problema de roteamento e alocação de comprimento de onda ou, simplesmente, problema RWA (Routing and Wavelentgh Assignment problem). Muitos estudos foram realizados com o objetivo de encontrar uma solução eficiente para esse problema, mas nem sempre é possível aliar bom desempenho com baixo tempo de execução, requisito fundamental em redes de telecomunicações. A técnica de algoritmo genético (AG) tem sido utilizada para encontrar soluções de problemas de otimização, como é o caso do problema RWA, e tem obtido resultados superiores quando comparada com soluções heurísticas tradicionais encontradas na literatura. Esta dissertação apresenta, resumidamente, os conceitos de redes ópticas e de algoritmos genéticos, e descreve uma formulação do problema RWA adequada à solução por algoritmo genético.

Síntese evolucionária de circuitos sequenciais inspirada nos princípios da computação quântica.

Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam uma classe de circuitos que é capaz de executar operações em uma determinada sequência. Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados na computação quântica como uma ferramenta para a síntese automática de circuitos sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados; (ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v) Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda sem solução. A atribuição de estados escolhida para uma determinada máquina de estados tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos de menor complexidade quando comparados com os circuitos gerados a partir de atribuições obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no projeto de circuitos eletrônicos.

Expert system for prestressed concrete bridge design

The development of an expert system, BRIDEX, for the design of prestressed concrete bridges is discussed in this paper. Design of multi-span continuous pre-stressed concrete bridges pose considerable difficulties to designers because of the large number of parameters involved and their complex interactions. The design is often perceived as an iterative process of generation, evaluation and modification of trial designs. It takes years of experience to develop an understanding of the design process. BRIDEX is aimed at providing guidance to the designers by suggesting appropriate range of values for the design parameters. The knowledge within BRIDEX is mainly based on fundamental principles developed by a careful study of the intricacies involved in the design process, while heuristics are used only to supplement this knowledge. The BRIDEX approach ensures that the whole design evolves sequentially as the design proceeds, module after module.