4599558
Pruning Update Log Files in Intermittently Connected Databases
Modern databases allow mobile clients that subscribe to replicated data, to process the replica without requiring continuous connectivity, and to receive the updates while connected to the server. In such an environment—usually known as the Intermittently Connected Database (ICDB) system—the server should maintain the updates to the database in the log file(s). These update log files should be pruned to reduce update retrieval time. In this paper we propose two pruning algorithms, based on the periodic connectivity of the clients, that consider two scenarios: uniform client connectivity patterns and widely varying client connectivity patterns. In the former case, the complete pruning algorithm is effective in keeping the log file size within a bound, hence reducing both disk I/O during update propagation, and disk storage space; whereas, in case of the latter, the partial pruning algorithm achieves significant further reduction in disk I/O while retrieving the updates. Any reduction in CPU or I/O time in turn reduces wireless connection time for each client resulting in significant savings in time and costs. Experimental results demonstrate the effectiveness of these algorithms.
28610861
A User Level, Reliable, and Reconfigurable Transport Layer Protocol
It is well known that TCP is not suitable for a number of environments such as wireless, satellite, and long-fat-pipe networks. At the same time, there is no other single transport protocol that would outperform TCP in all situations. In this paper, we explore an alternative transport layer protocol that is more suitable for today’s mobile as well as other non-conventional network environments. The result is a user-level, reconfigurable, TCP-friendly (asymptotically converges to fairness as in the case of LIMD (Linear Increase Multiplicative Decrease) algorithms) transport layer protocol, called RRTP (Reliable and Reconfigurable Transport Protocol), which runs atop of UDP. We evaluate our protocol using the standard network simulation tool (ns2). Several representative network configurations are used to benchmark the performance of our protocol against TCP in terms of network throughput and congestion loss rate. It is observed that under normal operating conditions, our protocol has a performance advantage of 30% to 700% over TCP in lossy, wireless environments as well as high bandwidth, high latency networks.
5517060
Structuring Distributed Algorithms in a Workstation Environment: The FrameWorks Approach
42975476
An Integrated Performance Analysis Tool for SPMD Data-Parallel Programs
Abstract A new generation of data parallel languages have been proposed whereby a user specifies how data structures are to be distributed amongst the processor nodes of a distributed-memory machine. Based on this information, the compiler then generates code for the parallel application. Although this approach significantly simplifies the development of the initial version of a parallel application, selection of good data distributions leading to efficient computations is often quite difficult. Therefore, performance debuggers are needed to yield insights into the data distribution effects. On the other hand, most of the existing approaches to performance debugging are very general and thus do not provide the user feedback in terms of the high level programming model or the source code of the parallel application. In this paper, we describe a novel approach to performance debugging of data parallel programs. The design and implementation of a visual performance debugger is described that is specifically targeted to meet the performance debugging requirements of a data-parallel programming model based on user-specified data distributions. The performance debugger is part of an integrated programming environment, called EPPP, which also supports a data parallel compiler and a parallel architecture simulator. Thus development and performance debugging of an application may be done either on the real hardware or by using the simulator. The code for EPPP can be obtained free of cost (contact web address, http://www.crim.ca/apar).
46262817
Extensible Parallel Architectural Skeletons
Complexity of parallel application development has been one of the major obstacles towards the mainstream adoption of parallel programming. In order to hide some of these complexities, researchers have been actively investigating the pattern-based approaches to parallel programming. As reusable components, patterns are intended to ease the design and development phases of parallel applications. Parallel Architectural Skeleton (PAS) is one such pattern-based parallel programming model which describes the architectural aspects of parallel patterns. Like many other pattern-based parallel programming models and tools, the benefits of PAS were offset by the difficulties in extending PAS. EPAS is an extension of PAS that addresses this issue. Using EPAS, a skeleton designer can design new skeletons and add them to the skeleton repository (i.e., extensibility). EPAS also makes the PAS model more flexible by defining composition of skeletons. In this paper, we describe the model of EPAS and also discuss some of the recent usability and performance studies. The studies demonstrate that EPAS is a practical and usable parallel programming model and tool.
62714434
Experience with parallel programming using code templates
For almost a decade we have been working at developing and using template-based models for parallel computing. Template-based models separate the speci cation of the parallel structuring aspects from the application code that is to be parallelized. A user provides the application code and speci es the parallel structure of the application using high-level icons, called templates. The parallel programming system then generates the code necessary for parallelizing the application. The goal here is to provide a mechanism for quick and reliable development of coarse-grain parallel applications that employ frequently occurring parallel structures. Our initial template-based system, FrameWorks, was positively received but had a number of shortcomings. The Enterprise parallel programming environment evolved out of this work. Now, after several years of experience with the system, its shortcomings are becoming evident. Controlled experiments have been conducted to assess the usability of our system in comparison with other systems. This paper outlines our experiences in developing and using these systems. A list of desirable characteristics of template-based models is given. FrameWorks and Enterprise systems are discussed in the context of these characteristics and the results of our usability experiments. Many of our observations are relevant to other parallel programming systems, even though they may be based on di erent assumptions. Although template-base models have the potential for simplifying the complexities of parallel programming, they have yet to realize these expectations for high-performance applications.
13609251
Creating an adaptive network of hubs using Schelling's model
Adjusting the overlay network topology in a peer-to-peer network to satisfy performance criteria.
2485299
Sizing CMOS circuits for increased transient error tolerance
The continuous shrinking of microelectronic device sizes with every technology generation, along with the reduction in supply voltages, is causing a significant decrease in circuit noise margins. This leads to increased susceptibility of circuits to transient errors. In this paper, we propose a methodology to increase the robustness of combinational circuits to transient errors by sizing the gates of the circuit in such a way that the number of errors propagated to the primary output is minimized while the timing requirement is met. Using SPICE simulation, we validate that combinational circuits propagate fewer numbers of transient errors to the circuit output after application of our sizing algorithm.
11606897
Malicious ICMP Tunneling: Defense against the Vulnerability
This paper presents a systematic solution to the problem of using ICMP tunneling for covert channel. ICMP is not multiplexed via port numbers and the data part of the ICMP packet provides considerable bandwidth for malicious covert channels. These factors make it an integral part of many malicious software like remote access and denial of service attack tools. These tools use ICMP to establish covert communication channels. In this paper a stateless model is proposed to prevent ICMP tunneling. A Linux kernel module was implemented to demonstrate the proposed stateless solution. The module enforces a fixed payload policy for ICMP packets and virtually eliminates ICMP tunneling which arises due to the data carrying capability of ICMP. The performance impact on end hosts and routers due to the stateless monitoring model is described.
9094346
Level-shifter free design of low power dual supply voltage CMOS circuits using dual threshold voltages
Usage of dual supply voltages in a digital circuit is an effective way of reducing the dynamic power consumption due to the quadratic relation of supply voltage to dynamic power consumption. But the need for level shifters when a low voltage gate drives a high voltage gate has been a limiting factor preventing widespread usage of dual supply voltages in digital circuit design. The overhead of level shifters forces designers to increase the granularity of dual voltage assignment, reducing the maximum obtainable savings. We propose a method of incorporating voltage level conversion into regular CMOS gates by using a second threshold voltage. Proposed level shifter design makes it possible to apply dual supply voltages at gate level granularity with much less overhead compared to traditional level shifters. We modify the threshold voltage of the high voltage gates that are driven by low voltage gates in order to obtain the level shifting operation together with the logic operation. Using our method, we obtained an average of 20% energy savings for ISCAS'85 benchmark circuits designed using 180-nm technology and 17% when 70-nm technology is used.
29012055
Variable Order Verification Use of Logic Representation
Boolean functions are fundamental to synthesis and verification of digital logic, and compact representations of Boolean functions have great practical significance. Conversion between those representations is common, especially when one is used to represent the input and another speeds up relevant algorithms. In the last 15 years, a number of applications based on efficient manipulation of Boolean functions gained industrial significance, notably in automated design and verification of logic circuits. The efficient representation and manipulation of Boolean functions is important for many algorithms in a wide variety of applications in particular, many problems in computer-aided design for digital circuits (CAD). The efficiency of the Boolean manipulation depends on the form of representation of the Boolean function. It is unavoidable and important problem to find a variable ordering which minimize the size of a BDD, since variable ordering has a great influence on the computation time and storage requirements for Boolean function manipulation number of times each variable takes part in the Logic operation to obtain the best possible the variable order. This paper describes a technique for finding the best variable ordering by analyzing the logic gate representation in the given Boolean function. Algorithm starts with initial variable ordering. The system will check each sub expression to find out the number times each variable takes part in each type of logic operations. The number of occurrences for each variable will be stored and then all the totals are arranged in descending order to identify the variable ordering for that Boolean function. If more than one input variables have the same total then a special criteria will be used to break the tie: We present graph-based evidence of the improvement obtained by using highly effective logical verification based variable ordering technique for BDDs. It is shown that the effectiveness of the Decision Diagram is mainly depending on the variable ordering selected. It is not practical to have any unique ordering for a given Boolean function and it can be selected among the number of best results, what will be more appropriate with the design. This new technique, easy to implement and automate, consistently creates high quality variable ordering for Boolean function.