The Message Passing Interface (MPI), which dominates the supercomputing programming environment, is used to orchestrate and fulfill communication in High Performance Computing (HPC). How far HPC programs can scale depends in large part on the ability to achieve fast communication; and to overlap communication with computation or communication with communication. This dissertation proposes a new asynchronous solution to the nonblocking Rendezvous protocol used between pairs of processes to transfer large payloads. On top of enforcing communication/computation overlapping in a comprehensive way, the proposal trumps existing network device-agnostic asynchronous solutions by being memory-scalable and by avoiding brute force strategies. Achieving overlapping between communication and computation is important; but each communication is also expected to generate minimal latency. In that respect, the processing of the queues meant to hold messages pending reception inside the MPI middleware is expected to be fast. Currently though, that processing slows down when program scales grow. This research presents a novel scalability-driven message queue whose processing skips altogether large portions of queue items that are deterministically guaranteed to lead to unfruitful searches. For having little sensitivity to program sizes, the proposed message queue maintains a very good performance, on top of displaying a low and flattening memory footprint growth pattern. Due to the blocking nature of its required synchronizations, the one-sided communication model of MPI creates both communication/computation and communication/communication serializations. This research fixes these issues and latency-related inefficiencies documented for MPI one-sided communications by proposing completely nonblocking and non-serializing versions for those synchronizations. The improvements, meant for consideration in a future MPI standard, also allow new classes of programs to be more efficiently expressed in MPI. Finally, a persistent distributed service is designed over MPI to show its impacts at large scales beyond communication-only activities. MPI is analyzed in situations of resource exhaustion, partial failure and heavy use of internal objects for communicating and non-communicating routines. Important scalability issues are revealed and solution approaches are put forth. / Thesis (Ph.D, Electrical & Computer Engineering) -- Queen's University, 2014-05-23 15:08:58.56

In recent years, social networks have become an important part of our daily lives. Billions of people daily use Facebook and other prominent social media networks. This makes them an effective medium for advertising and marketing. Finding the most influential users in a social network is an interesting problem in this domain, as promoters can reach large audiences by targeting these few influential users. This is the influence maximization problem, where we want to maximize the influence spread using as few users as possible. As these social networks are huge, scalability and runtime of the algorithm to find the most influential users is of high importance. We propose innovative improvements in the implementation of the state-of-the-art sketching algorithm for influence analysis on social networks. The primary goal of this thesis is to make the algorithm fast, efficient, and scalable. We devise new data structures to improve the speed of the sketching algorithm. We introduce the compressed version of the algorithm which reduces the space taken in the memory by the data structures without compromising the runtime. By performing extensive experiments on real-world graphs, we prove that our algorithms are able to compute the most influential users within a reasonable amount of time and space on a consumer grade machine. These modifications can further be enhanced to reflect the constantly updating social media graphs to provide accurate estimations in real-time. / Graduate

There has been a growing demand to manage bandwidth as the network traffic increases. Network applications such as real time video streaming, voice over IP and video conferencing in IP networks has risen rapidly over the recently and is projected to continue in the future. These applications consume a lot of bandwidth resulting in increasing pressure on the networks. In dealing with such challenges, modern networks must be designed to be application sensitive and be able to offer Quality of Service (QoS) based on application requirements. Network paradigms such as Software Defined Networking (SDN) allows for direct network programmability to change the network behavior to suit the application needs in order to provide solutions to the challenge. In this dissertation, the objective is to research if SDN can provide scalable QoS requirements to a set of dynamic traffic flows. Methods are implemented to attain scalable bandwidth management to provide high QoS with SDN. Differentiated Services Code Point (DSCP) values and DSCP remarking with Meters are used to implement high QoS requirements such that bandwidth guarantee is provided to a selected set of traffic flows. The theoretical methodology is implemented for achieving QoS, experiments are conducted to validate and illustrate that QoS can be implemented in SDN, but it is unable to implement High QoS due to the lack of implementation for Meters with DSCP remarking. The research work presented in this dissertation aims at the identification and addressing the critical aspects related to the SDN based QoS provisioning using flow aggregation techniques. Several tests and demonstrations will be conducted by utilizing virtualization methods. The tests are aimed at supporting the proposed ideas and aims at creating an improved understanding of the practical SDN use cases and the challenges that emerge in virtualized environments. DiffServ Assured Forwarding is chosen as a QoS architecture for implementation. The bandwidth management scalability in SDN is proved based on throughput analysis by considering two conditions i.e 1) Per-flow QoS operation and 2) QoS by using DiffServ operation in the SDN environment with Ryu controller. The result shows that better performance QoS and bandwidth management is achieved using the QoS by DiffServ operation in SDN rather than the per-flow QoS operation.

Cloud computing is the current need and the futuristic strategy of many businesses. Economy and scalability are inevitable because they impact the flourishing of all online businesses. The objective of this study is to distinguish the differences between Amazon Lambda versus EKS and ECS using EC2 instances from the Economy and scalability perspectives. The study aims to give programmers without prior knowledge about the services an overall picture of their billing models, scalability,  and the goal each service is meant to deliver. A literature review was used to identify the related studies done earlier in this area of research. The data captured from the literature studies were enriched with an empirical study, namely, survey research  with semi-structured interviews. Snowballing was used to identify more interviewees with the help of the earlier selected respondents. After conducting the semi-structured online interviews with five participants, the recordings were transcribed. Finally, the Thematic Analysis approach was used to analyze the collected qualitative data from the transcripts. It was concluded that Lambda was useful for infrequent and minor workloads without long processing tasks, with a  free automatic and managed scalability. For websites doing massive processing or getting large requests constantly, EKS or ECS would be a better choice. However, ECS and EKS cost more than Lambda when working with smaller workloads. EKS has multi-direction scalability, making it more flexible than Lambda and ECS. However, this comes with additional costs and complexity, but it is cost-effective for bigger businesses. Ultimately, in real-world cloud architecture, it is relatively common to rely on a combination of cloud services to fulfill the economic or auto scalability objectives of a business instead of a single one.

Provedores de serviços de nuvem disponibilizam uma interface através da qual seus clientes podem solicitar, usar e liberar estes recursos. Muitos serviços implantados em nuvens incluem um componente para gerenciamento automatizado de recursos, encarregado de requisitar e librar recursos sem intervenção humana, à medida que a demanda varia. A técnica padrão para o gerenciamento de recursos se baseia em regras sobre utilização de recursos. Quando ocorre um aumento significativo na carga em um curto espaço de tempo, o sistema pode levar vários ciclos de monitoramento e ação até alcançar uma configuração adequada. Neste período, o sistema permanece sobrecarregado. Nesta pesquisa, investigamos como compreender adequadamente os efeitos da variação na disponibilidade de recursos sobre a capacidade de um sistema e como aplicar este conhecimento para melhorar sua elasticidade. Propomos uma estratégia que abrange avaliação da escalabilidade do sistema, visando sua modelagem, e a aplicação deste modelo nas estimativas de necessidade por recursos com base na carga de trabalho. Introduzimos um arcabouço para automatizar a avaliação de escalabilidade de sistemas distribuídos e efetuamos uma validação experimental da estratégia proposta. Comparamos a alocação de recursos e o desempenho obtido usando nossa estratégia e estratégia baseada em regras, fazendo a reprodução de carga real e usando cargas sintéticas. De forma geral, nossa proposta foi capaz de prover melhor desempenho, ao ponto que o uso de recursos cresceu, e consequentemente o custo de utilização. No entanto, a melhora de desempenho foi mais significativa que o aumento dos custos. / Cloud computing is a new paradigm in which virtual resources are leased in the short-term. Cloud providers publish an API through which users can request, use, and release those resources. Thus, a properly architected system can be quickly deployed and their infrastructure can be quickly updated to better accommodate workload fluctuations and limit expenses. Many services running in clouds comprise an automated resource management unit, which is in charge of requesting and releasing resources without human intervention, as demand changes. The rule based approach, commonlly applied to automate the resource management, is especially problematic in cases of load surge. When of a quick and drastic increase of the workload, the system may take many cycles of infrastructural redimensioning until achieve an adequate state. In this case, the system remains overloaded during all those cycles, affecting user experience. In this research, we investigate how we can properly understand what are the effects, in system capacity, incurred by variations in resource availability, and how this knowledge can be applied to improve elasticity. We propose a strategy that comprises performing scalability tests to model scalability and apply the model to estimate resource need, according to the arriving workload. We introduce a framework for automated scalability evaluation of distributed systems and experimentally evaluate the proposed strategy. We compare the allocation and performance obtained using our strategy with a rule based strategy in a trace-driven simulation and with synthetic workloads. We also evaluate six variations of the model-based approach. Generally, our approach can deliver better performance, while increasing resource allocation and, consequently, cost. The extent of the performance improvement is larger than the cost increment, though.

Provedores de serviços de nuvem disponibilizam uma interface através da qual seus clientes podem solicitar, usar e liberar estes recursos. Muitos serviços implantados em nuvens incluem um componente para gerenciamento automatizado de recursos, encarregado de requisitar e librar recursos sem intervenção humana, à medida que a demanda varia. A técnica padrão para o gerenciamento de recursos se baseia em regras sobre utilização de recursos. Quando ocorre um aumento significativo na carga em um curto espaço de tempo, o sistema pode levar vários ciclos de monitoramento e ação até alcançar uma configuração adequada. Neste período, o sistema permanece sobrecarregado. Nesta pesquisa, investigamos como compreender adequadamente os efeitos da variação na disponibilidade de recursos sobre a capacidade de um sistema e como aplicar este conhecimento para melhorar sua elasticidade. Propomos uma estratégia que abrange avaliação da escalabilidade do sistema, visando sua modelagem, e a aplicação deste modelo nas estimativas de necessidade por recursos com base na carga de trabalho. Introduzimos um arcabouço para automatizar a avaliação de escalabilidade de sistemas distribuídos e efetuamos uma validação experimental da estratégia proposta. Comparamos a alocação de recursos e o desempenho obtido usando nossa estratégia e estratégia baseada em regras, fazendo a reprodução de carga real e usando cargas sintéticas. De forma geral, nossa proposta foi capaz de prover melhor desempenho, ao ponto que o uso de recursos cresceu, e consequentemente o custo de utilização. No entanto, a melhora de desempenho foi mais significativa que o aumento dos custos. / Cloud computing is a new paradigm in which virtual resources are leased in the short-term. Cloud providers publish an API through which users can request, use, and release those resources. Thus, a properly architected system can be quickly deployed and their infrastructure can be quickly updated to better accommodate workload fluctuations and limit expenses. Many services running in clouds comprise an automated resource management unit, which is in charge of requesting and releasing resources without human intervention, as demand changes. The rule based approach, commonlly applied to automate the resource management, is especially problematic in cases of load surge. When of a quick and drastic increase of the workload, the system may take many cycles of infrastructural redimensioning until achieve an adequate state. In this case, the system remains overloaded during all those cycles, affecting user experience. In this research, we investigate how we can properly understand what are the effects, in system capacity, incurred by variations in resource availability, and how this knowledge can be applied to improve elasticity. We propose a strategy that comprises performing scalability tests to model scalability and apply the model to estimate resource need, according to the arriving workload. We introduce a framework for automated scalability evaluation of distributed systems and experimentally evaluate the proposed strategy. We compare the allocation and performance obtained using our strategy with a rule based strategy in a trace-driven simulation and with synthetic workloads. We also evaluate six variations of the model-based approach. Generally, our approach can deliver better performance, while increasing resource allocation and, consequently, cost. The extent of the performance improvement is larger than the cost increment, though.

The exponential improvement in single processor performance has recently come to an end, mainly because clock frequency has reached its limit due to power constraints. Thus, processor manufacturers are choosing to enhance computing capabilities by placing multiple cores into a single chip, which can improve performance given parallel software. This paradigm shift to chip multiprocessors (also called multicore) requires scalable parallel applications that execute tasks on each core, otherwise the additional cores are worthless. Making an application scalable requires more than simply parallelizing the application code itself. Modern applications are written in managed languages, which require automatic memory management, type and memory abstractions, dynamic analysis and just-in-time (JIT) compilation. These managed runtime systems monitor and interact frequently with the executing application. Hence, the managed runtime itself must be scalable, and the instrumentation that monitors the application should not perturb its scalability. While multicore hardware forces a redesign of managed runtimes for scalability, it also provides opportunities when applications do not fully utilize all of the cores. Using available cores for concurrent helper threads that enhance the software, with debugging, security, and software support will make the runtime itself more capable and more scalable. This dissertation presents two novel techniques that improve the scalability of managed runtimes by utilizing unused cores. The first technique is a concurrent dynamic analysis framework that provides a low-overhead buffering mechanism called Cache-friendly Asymmetric Buffering (CAB) that quickly offloads data from the application to helper threads that perform specific dynamic analyses. Our framework minimizes application instrumentation overhead, prevents microarchitectural side-effects, and supports a variety of dynamic analysis clients, ranging from call graph and path profiling to cache simulation. The use of this framework ensures that helper threads perturb the performance of application as little as possible. Our second technique is concurrent trace-based just-in-time compilation, which exploits available cores for the JavaScript runtime. The JavaScript language limits applications to a single-thread, so extra cores are worthless unless they are used by the runtime components. We redesigned a production trace-based JIT compiler to run concurrently with the interpreter, and our technique is the first to improve both responsiveness and throughput in a trace-based JIT compiler. This thesis presents the design and implementation of both techniques and shows that they improve scalability and core utilization when running applications in managed runtimes. Industry is already adopting our approaches, which demonstrates the urgency of the scalable runtime problem and the utility of these techniques. / text

Computational imaging and sensing leverages the joint-design of optics, detectors and processing to overcome the performance bottlenecks inherent to the traditional imaging paradigm. This novel imaging and sensing design paradigm essentially allows new trade-offs between the optics, detector and processing components of an imaging system and enables broader operational regimes beyond the reach of conventional imaging architectures, which are constrained by well-known Rayleigh, Strehl and Nyquist rules amongst others. In this dissertation, we focus on scalability aspects of these novel computational imaging architectures, their design and implementation, which have far-reaching impacts on the potential and feasibility of realizing task-specific performance gains relative to traditional imager designs. For the extended depth of field (EDoF) computational imager design, which employs a customized phase mask to achieve defocus immunity, we propose a joint-optimization framework to simultaneously optimize the parameters of the optical phase mask and the processing algorithm, with the system design goal of minimizing the noise and artifacts in the final processed image. Using an experimental prototype, we demonstrate that our optimized system design achieves higher fidelity output compared to other static designs from the literature, such as the Cubic and Trefoil phase masks. While traditional imagers rely on an isomorphic mapping between the scene and the optical measurements to form images, they do not exploit the inherent compressibility of natural images and thus are subject to Nyquist sampling. Compressive sensing exploits the inherent redundancy of natural images, basis of image compression algorithms like JPEG/JPEG2000, to make linear projection measurements with far fewer samples than Nyquist for the image forming task. Here, we present a block wise compressive imaging architecture which is scalable to high space-bandwidth products (i.e. large FOV and high resolution applications) and employs a parallelizable and non-iterative piecewise linear reconstruction algorithm capable of operating in real-time. Our compressive imager based on this scalable architecture design is not limited to the imaging task and can also be used for automatic target recognition (ATR) without an intermediate image reconstruction. To maximize the detection and classification performance of this compressive ATR sensor, we have developed a scalable statistical model of natural scenes, which enables the optimization of the compressive sensor projections with the Cauchy-Schwarz mutual information metric. We demonstrate the superior performance of this compressive ATR system using simulation and experiment. Finally, we investigate the fundamental resolution limit of imaging via the canonical incoherent quasi-monochromatic two point-sources separation problem. We extend recent results in the literature demonstrating, with Fisher information and estimator mean square error analysis, that a passive optical mode-sorting architecture with only two measurements can outperform traditional intensity-based imagers employing an ideal focal plane array in the sub-Rayleigh range, thus overcoming the Rayleigh resolution limit.

The Internet currently supports a best-effort connectivity service. There has been an increasing demand for the Internet to support Quality of Service (QoS) to satisfy stringent service requirements from many emerging networking applications and yet to utilize the network resources efficiently. However, it has been found that even with augmented QoS architecture, the Internet cannot achieve the desired QoS and furthermore, there are concerns about the scalability of any available QoS solutions. If the network is not provisioned adequately, the Internet is not capable to handle congestion condition. This is because the Internet is unaware of its internal network QoS states therefore it is not possible to provide QoS when the network state changes dynamically. This thesis addresses the following question: Is it possible to deliver the applications with QoS in the Internet fairly and efficiently while keeping scalability? In this dissertation we answer this question affirmatively by proposing an innovative service architecture: the Resource Discovery (RD) and Fair Intelligent Admission Control (FIAC) over scalable Internet. The main contributions of this dissertation are as follows: 1. To detect the network QoS state, we propose the Resource Discovery (RD) framework to provide network QoS state dynamically. The Resource Discovery (RD) adopts feedback loop mechanism to collect the network QoS state and reports to the Fair Intelligent Admission Control module, so that FIAC is capable to take resource control efficiently and fairly. 2. To facilitate network resource management and flow admission control, two scalable Fair Intelligent Admission Control architectures are designed and analyzed on two levels: per-class level and per-flow level. Per-class FIAC handles the aggregate admission control for certain pre-defined aggregate. Per-flow FIAC handles the flow admission control in terms of fairness within the class. 3. To further improve its scalability, the Edge-Aware Resource Discovery and Fair Intelligent Admission Control is proposed which does not need the core routers involvement. We devise and analyze implementation of the proposed solutions and demonstrate the effectiveness of the approach. For the Resource Discovery, two closed-loop feedback solutions are designed and investigated. The first one is a core-aware solution which is based on the direct QoS state information. To further improve its scalability, the edge-aware solution is designed where only the edges (not core)are involved in the feedback QoS state estimation. For admission control, FIAC module bridges the gap between 'external' traffic requirements and the 'internal' network ability. By utilizing the QoS state information from RD, FIAC intelligently allocate resources via per-class admission control and per-flow fairness control. We study the performance and robustness of RD-FIAC through extensive simulations. Our results show that RD can obtain the internal network QoS state and FIAC can adjust resource allocation efficiently and fairly.

Many online services access a large number of autonomous data sources and at the same time need to meet different user requirements. It is essential for these services to achieve semantic interoperability among these information exchange entities. In the presence of an increasing number of proprietary business processes, heterogeneous data standards, and diverse user requirements, it is critical that the services are implemented using adaptable, extensible, and scalable technology. The COntext INterchange (COIN) approach, inspired by similar goals of the Semantic Web, provides a robust solution. In this paper, we describe how COIN can be used to implement dynamic online services where semantic differences are reconciled on the fly. We show that COIN is flexible and scalable by comparing it with several conventional approaches. With a given ontology, the number of conversions in COIN is quadratic to the semantic aspect that has the largest number of distinctions. These semantic aspects are modeled as modifiers in a conceptual ontology; in most cases the number of conversions is linear with the number of modifiers, which is significantly smaller than traditional hard-wiring middleware approach where the number of conversion programs is quadratic to the number of sources and data receivers. In the example scenario in the paper, the COIN approach needs only 5 conversions to be defined while traditional approaches require 20,000 to 100 million. COIN achieves this scalability by automatically composing all the comprehensive conversions from a small number of declaratively defined sub-conversions. / Singapore-MIT Alliance (SMA)