A fundamental capability of cloud computing is elasticity, i.e., the ability to dynamically change the amount of allocated resources. This is typically done by adjusting the number of Virtual Machines (VMs) running a service based on the current demand for that service. For large services, centralized management is impractical and distributed methods are employed. In such settings, no single component has full information on the overall demand and service quality, thus elasticity becomes a real challenge. We address this challenge by proposing a novel elasticity scheme that enables fully distributed management of large cloud services. Our scheme is based on three main components, namely, a task assignment policy, a VM scale-up policy and a VM scale-down policy. The task assignment policy strives to “pack” VMs while maintaining SLA requirements. The VM scale-up policy is based on local activation of new VMs and the VM scale-down policy is based on self-deactivation of VMs that are idle for some duration of time. Through simulations and an implementation we establish that our scheme quickly adapts to changes in job arrival rates and minimizes the number of active VMs so as to reduce the operational costs of the service, while adhering to strict SLA requirements.

Load balancing of large distributed server systems is a complex optimization problem of critical importance in cloud systems and data centers. Existing schedulers often incur a high communication overhead when collecting the data required to make scheduling decisions, hence delaying job requests on their way to the executing servers. We propose a novel scheme that incurs no communication overhead between the users and the servers upon job arrival, thus removing any scheduling overhead from the job's critical path. Our approach is based on creating several replicas of each job and sending each replica to a different server. Upon the arrival of a replica to the head of the queue at its server, the latter signals the servers holding replicas of that job, so as to remove them from their queues. We show, through analysis and simulations, that this scheme significantly improves the expected queuing overhead over traditional schemes under various load conditions and different job length distributions. In addition, we show that our scheme remains efficient even when the inter-server signal propagation delay is significant (relative to the job's execution time). We provide a heuristic solution to the performance degradation that occurs in such cases and show, by simulations, that it efficiently mitigates the detrimental effect of propagation delays.

Resource allocation and management in Cloud Computing is a very complex task. This is mainly due to the scale of the cloud and the number of services deployed in it. Since cloud users and service providers are given access to supercomputerlevel resources, their effect over the cloud's overall performance is greater than ever. This raises multiple research questions related to the management and performance of cloud computing systems in light of the end-users selfishness. In this work we specifically study the overall performance when selfish service providers may split work between the (shared) cloud and private resources. The size of modern data center and the number of service housed in it calls for fully distributed management solutions. We propose task assignment policies that are specifically adequate for large-scale distributed systems, and show that they provide new capabilities in improving system performance. In particular, we develop new resource allocation algorithms that converge to a working point that balances the end-user experience with the operational costs of leasing resources from the cloud provider.

Contention among users utilizing a single shared resource arises in multiple contexts of computing and computer communications. We consider a setup in which users can split their work between a shared resource and a private resource. Unlike the private resource, which provides guaranteed performance, the performance of the shared resource is highly dependent on the usage pattern of other users, which in turn influences a user's decision if and to what extent to make use of the shared resource. The intrinsic relation between the utility that a user perceives from the shared resource and the usage pattern followed by other users gives rise to a noncooperative game, which we model and investigate. We show that the considered game admits a Nash equilibrium. Moreover, we show that this equilibrium is unique. We investigate the ratio between the worst Nash equilibrium and the social optimum, known as the “price of anarchy,” and show that, while in some cases of interest the Nash equilibrium coincides with a social optimum, in other cases the price of anarchy can be arbitrarily large. We demonstrate that, somewhat counterintuitively, exercising admission control to the shared resource may deteriorate its performance. Furthermore, we demonstrate that certain (heavy) users may “scare off” other, potentially large, communities of users. Accordingly, we propose a resource allocation scheme that addresses this problem and opens the shared resource to a wide range of user types.

Transactional memory is a promising mechanism for synchronizing concurrent programs that eliminates locks at the expense of hardware complexity. Transactional memory is a hard feature to verify. First, transactions comprise several instructions that must be observed as a single global atomic operation. In addition, there are many reasons a transaction can fail. This results in a high level of non-determinism which must be tamed by the verification methodology. This paper describes the innovation that was applied to tools and methodology in pre-silicon simulation, acceleration and post-silicon in order to verify transactional memory in the IBM POWER8 processor core.

The post-silicon validation phase in a processor's design life cycle is geared towards finding all remaining bugs in the system. It is, in fact, our last opportunity to find functional and electrical bugs in the design before shipping it to customers.

In post-silicon functional validation, one of the most complex and time-consuming processes is the localization of an instruction that exposes a bug detected at system level. The task is particularly difficult due to the silicon's limited observability and the long time between a failure's occurrence and its detection. We propose a novel method that automates the architectural localization of post-silicon test-case failures. Our proposed tool analyzes a failing test-case, while leveraging the information derived from executing the test on an Instruction Set software Simulator (ISS), to identify a set of instructions that could lead to the faulty final state. The proposed failure localization process comprises the creation of a resource dependency graph based on the execution of the test-case on the ISS, determining a program slice of instructions that influence the faulty resources, and the reduction of the set of suspicious instructions by leveraging the knowledge of the correct resources. We evaluate our proposed solution through extensive experiments. Experimental results show that, in over 97% of all cases, our method was able to narrow down the list of suspicious instructions to under 2 instructions, on average, out of over 200. In over 59% of all cases, our method correctly reduced a test-case to a single faulty instruction.

We study the performance of noncooperative networks in light of three major topology design considerations, namely the price of establishing a link, path delay, and path proneness to congestion, the latter being modeled through the “relaying extent” of the nodes. We analyze these considerations and the tradeoffs between them from a game-theoretic perspective, where each network element attempts to optimize its individual performance. We show that for all considered cases but one, the existence of a Nash equilibrium point is guaranteed. For the latter case, we indicate, by simulations, that practical scenarios tend to admit a Nash equilibrium. In addition, we demonstrate that the price of anarchy, i.e., the performance penalty incurred by noncooperative behavior, may be prohibitively large; yet, we also show that such games usually admit at least one Nash equilibrium that is system-wide optimal, i.e., their price of stability is 1. This finding suggests that a major improvement can be achieved by providing a central (“social”) agent with the ability to impose the initial configuration on the system.

Software-based simulation provides a convenient environment for microprocessor design validation, where a number of complex software checkers are integrated with the simulated design to identify discrepancies between design and specification. Unfortunately, the performance of software-based simulation is vastly inadequate to achieve sufficient coverage for large microprocessor designs with complex microarchitectures. Hence, acceleration and emulation platforms are heavily deployed in the industry for high-performance validation. However, software checkers cannot be directly incorporated into such platforms, forcing designers to craft ad-hoc solutions. Adapting checking solutions for software simulation to acceleration platforms presents the following constraints: i) only a limited number of signals can be monitored per cycle for checking purposes so as to retain acceptable simulation performance, and ii) the overhead of the added checking logic must be minimal. In this work, we explore a novel solution to adapt software-based checkers for individual microarchitectural blocks to acceleration platforms, by leveraging a hybrid approach. Our solution exploits embedded logic and data tracing for post-simulation checking in a synergistic fashion to limit the associated overhead. Embedded logic can be used for synthesized local checkers as well as to compress the traced data and thus limit recording overhead. We analyze several trade-offs associated with checking accuracy and logic / recording overhead for different microarchitectural blocks of an out-of-order superscalar processor design. We strive to provide valuable insights on how to adapt such software checkers to the acceleration environment using our hybrid approach. We find that, by leveraging simple embedded checkers and data compressors (15-25% logic overhead), we can achieve excellent checking accuracy even when aggressively compressing the data for transfer (only 15-25 bits/cycle), and localize bugs up to 5,900 cycles sooner than an architectural-level checker.

Load balancing in large distributed server systems is a complex optimization problem of critical importance in cloud systems and data centers. Existing schedulers often incur a high overhead in communication when collecting the data required to make the scheduling decision, hence delaying the job request on its way to the executing server. We propose a novel scheme that incurs no communication overhead between the users and the servers upon job arrival, thus removing any scheduling overhead from the job's critical path. Our approach is based on creating several replicas of each job and sending each replica to a different server. Upon the arrival of a replica to the head of the queue at its server, the latter signals the servers holding replicas of that job, so as to remove them from their queues. We show, through analysis and simulations, that this scheme improves the expected queuing overhead over traditional schemes by a factor of 9 (or more) under various load conditions. In addition, we show that our scheme remains efficient even when the inter-server signal propagation delay is significant (relative to the job's execution time). We provide heuristic solutions to the performance degradation that occurs in such cases and show, by simulations, that they efficiently mitigate the detrimental effect of propagation delays. Finally, we demonstrate the efficiency of our proposed scheme in a real-world environment by implementing a load balancing system based on it, deploying the system on the Amazon Elastic Compute Cloud (EC2), and measuring its performance.

The role of stimuli generators is to reach all the dark corners of the design and expose the bugs hiding there. As such, stimuli generation is one of the cornerstones of dynamic verification. The quality of tools used for stimuli generation affect the outcome of the verification process. This paper discusses how differences between execution platforms, ranging from software simulators, through accelerators and emulators, to silicon affect the requirements of stimuli generators and how stimuli generators targeting different execution platforms address these differences. We demonstrate how the unique added value of the platforms are combined to guarantee the high quality of the silicon using examples of several IBM pre- and post-silicon stimuli generators with results from the verification of the IBM POWER7 processor chip.

Simulation-based functional verification is the key validation methodology the industry. The performance of logic simulators, however, is not sufficient to attain acceptable verification coverage on large industrial designs within the time-frame available. Acceleration platforms are a valuable addition to the verification effort in that they can provide much higher coverage in less time. Unfortunately, these platforms do not provide the rich checking capability of software-based simulation. We propose a novel solution to deploy those complex checkers, typical of simulation-based environments, onto acceleration platforms. To this end, checkers must be transformed into synthesizable, compact logic blocks with bug-detection capabilities similar to that of their software counterparts. Our “approximate checkers” trade off logic complexity with bug detection accuracy by leveraging novel techniques to approximate complex software checkers into small synthesizable hardware blocks, which can be simulated along with the design on an acceleration platform. We present a general checker taxonomy, propose a range of approximation techniques based on a checker's characteristic and provide metrics for evaluating its bug detection capabilities.

Cloud computing is an emerging paradigm in which tasks are assigned to a combination (“cloud”) of servers and devices, accessed over a network. Typically, the cloud constitutes an additional means of computation and a user can perform workload factoring, i.e., split its load between the cloud and its other resources. Based on empirical data, we demonstrate that there is an intrinsic relation between the “benefit” that a user perceives from the cloud and the usage pattern followed by other users. This gives rise to a non-cooperative game, which we model and investigate. We show that the considered game admits a Nash equilibrium. Moreover, we show that this equilibrium is unique. We investigate the “price of anarchy” of the game and show that, while in some cases of interest the Nash equilibrium coincides with a social optimum, in other cases the gap can be arbitrarily large. We show that, somewhat counter-intuitively, exercising admission control to the cloud may deteriorate its performance. Furthermore, we demonstrate that certain (heavy) users may “scare off” other, potentially large, communities of users. Accordingly, we propose a resource allocation scheme that addresses this problem and opens the cloud to a wide range of user types.

The continuing trend toward increased parallelism in processor design can be seen in both the growing number of processor cores per system and in on-core hardware mechanisms that assist parallelism, such as multithreading and cache hierarchies. This complexity exacerbates the problem of ensuring the functional correctness of such hardware systems. The growing importance of post-silicon validation is leading to an emerging type of parallel application, namely, the hardware exerciser. We describe a method for exercising parallel hardware by generating pseudorandom concurrent test programs. The test generation is carried out on the tested parallel platform and thus the generator itself is also a concurrent program. We describe the challenges associated with this technology and the approach used by the Threadmill hardware exerciser, a tool developed for the post-silicon validation of the IBM POWER7 processor.

Post-silicon validation poses unique challenges that bring-up tools must face, such as the lack of observability into the design, the typical instability of silicon bring-up platforms and the absence of supporting software (like an OS or debuggers). These challenges and the need to reach an optimal utilization of the expensive but very fast silicon platforms lead to unique design considerations - like the need to keep the tool simple and to perform most of its operation on platform without interaction with the environment.

The growing importance of post-silicon validation in ensuring functional correctness of high-end designs has increased the need for synergy between the pre-silicon verification and post-silicon validation. This synergy starts with a common verification plan. It continues with common verification goals and shared tools and techniques. This paper describes our experience in improving this synergy in the pre- and post-silicon verification of IBM's POWER7 processor chip and by leveraging pre-silicon methodologies and techniques in the post-silicon validation of the chip.

This paper presents TAB-BackSpace, our novel scheme to provide the effect of an unlimited-length trace buffer with no on-chip overhead beyond the existing debug logic. We present the theoretical foundation of our work, simulation studies on how we reduce the possibility of computing an erroneous trace, and results from the bring-up lab on real silicon of an IBM POWER7 processor, where TAB-BackSpace computes almost a thousand additional cycles of trace buffer information without any additional on-chip overhead.

The growing importance of post-silicon validation in ensuring functional correctness of high-end designs increases the need for synergy between the pre-silicon verification and post-silicon validation. We propose a unified functional verification methodology for the pre- and post-silicon domains. This methodology is based on a common verification plan and similar languages for test-templates and coverage models. Implementation of the methodology requires a user-directable stimuli generation tool for the post-silicon domain. We analyze the requirements for such a tool and the differences between it and its pre-silicon counterpart. Based on these requirements, we implemented a tool called Threadmill and used it in the verification of the IBM POWER7 processor chip with encouraging results.

Post-silicon validation is a necessary step in a design's verification process. Pre-silicon techniques such as simulation and emulation are limited in scope and volume as compared to what can be achieved on the silicon itself. Some parts of the verification, such as full-system functional verification, cannot be practically covered with current pre-silicon technologies. This panel brings together experts from industry, academia, and EDA to review the differences and similarities between pre- and post-silicon, discuss how the fundamental aspects of verification are affected by these differences, and explore how the gaps between the two worlds can be bridged.

Monitoring is an essential part of any self-adaptive management loop. While providing the necessary information for making management decisions, monitoring itself incurs a cost in terms of the system and network resources committed to this management task. Thus, one can pose a generic question: what is the right amount of monitoring that maximizes its utility for management? This question turns out to be difficult to answer in general. In this paper we focus on quantifying the utility of monitoring for self-adaptive load sharing, where a stream of jobs arrives at a collection of n identical servers. We propose a novel model, that we dubbed an Extended Supermarket Model (ESM) to study the tradeoff between the usefulness of the monitoring information and the cost of obtaining it. We show that for each service request rate, there exists an optimal number of servers that should be monitored to obtain minimal average service time at an optimal cost. Using these findings, we present self-adaptive load-sharing algorithms both for centralized and fully distributed settings and evaluate these algorithms using simulations and a real testbed. Our results show that in realistic scenarios, where monitoring cost is not negligible, the self-adaptive load balancing is clearly superior to any cost-oblivious load-sharing mechanisms. We also demonstrate that in a fully distributed setting, where no dedicated monitoring component is employed, our self-adaptive heuristics perform very well with respect to the current common practice.

We study the performance of non-cooperative networks in light of three major topology design and control considerations, namely the price of establishing a link, path delay, and path proneness to congestion or interference, the latter being modeled through the "relaying extent" of the nodes. We analyze these considerations and the tradeoffs between them from a game theoretic perspective, where each network element attempts to optimize its individual performance. We show that for all considered cases but one, the existence of a Nash equilibrium point is guaranteed. In addition, we demonstrate that the price of anarchy, i.e., the performance penalty incurred by non-cooperative behavior, may be prohibitively large; yet, we also show that such games usually admit at least one Nash equilibrium that is system-wide optimal, i.e., their price of stability is 1. This finding suggests that a major improvement can be achieved by providing a central ("social") agent with the ability to impose the initial configuration on the system.

Multimedia SoCs are characterized by a main controller that directs the activity of several cores, each of which is in charge of a stage in the processing of a media stream. The verification of these SoCs is a significant challenge due to time-to-market constraints and system complexity. We present a novel approach to system-level, random test case generation for multimedia SoCs, and a tool, called SoCVer, that implements this approach. We use the SoC's main controller point of view for controlling the flow of data in the SoC. Test case generation is done by allocating processing tasks to the various cores and determining which core processes which data item at what time. Solving these scheduling problems allows SoCVer to generate software for the SoC's main controller; this software coordinates and synchronizes the operations of all the cores on the chip without the need for the real operational software. We demonstrate the use of SoCVer using a DVD player SoC.