15969885
Optimistic register coalescing
Graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. Coalescing, however, can be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. Unlike aggressive coalescing, which coalesces any pair of noninterfering copy-related nodes, conservative coalescing or iterated coalescing perform safe coalescing that preserves the colorability. Unfortunately, these heuristics give up coalescing too early, losing many opportunities for coalescing that would turn out to be safe. Moreover, they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. This article proposes a new heuristic called optimistic coalescing which optimistically performs aggressive coalescing, thus exploiting the positive impact of coalescing aggressively, but when a coalesced node is to be spilled, it is split back into separate nodes. Since there is a better chance of coloring one of those splits, we can reduce the overall spill amount.
1748996
Reducing sweep time for a nearly empty heap
Mark and sweep garbage collectors are known for using time proportional to the heap size when sweeping memory, since all objects in the heap, regardless of whether they are live or not, must be visited in order to reclaim the memory occupied by dead objects. This paper introduces a sweeping method which traverses only the live objects, so that sweeping can be done in time dependent only on the number of live objects in the heap.
This allows each collection to use time independent of the size of the heap, which can result in a large reduction of overall garbage collection time in empty heaps. Unfortunately, the algorithm used may slow down overall garbage collection if the heap is not so empty. So a way to select the sweeping algorithm depending on the heap occupancy is introduced, which can avoid any significant slowdown.
32135793
Split-Path Enhanced Pipeline Scheduling
Software pipelining increases the loop execution throughput by overlapping the execution of successive iterations in a pipelined fashion. For loops with control flows, however, software pipelining is not straightforward because we need to consider the overlap of more than one execution path. Modulo scheduling simply transforms them into straightline loops through if-conversion which, in effect, achieves a fixed, worst-case initiation interval (/spl par/) among all paths. On the other hand, all-path pipelining (APP) and enhanced pipeline scheduling (EPS) can achieve a variable /spl par/ depending on the path that is taken at execution time. Unfortunately, APP concentrates only on the overlap within the same path, entirely losing the overlap between different paths, whereas EPS attempts to overlap all paths together, failing to produce a tight schedule for each individual path, especially when resource constraints are tight. In this paper, we propose a new approach to EPS called split-path EPS (SP-EPS), which first splits each individual path via tail duplication and then performs EPS in a way to guarantee a tight schedule for each path, while producing a competitive cross-path schedule. We also extend SP-EPS to outer loops such that frequent paths that bypass the inner loop are split and then scheduled by SP-EPS. Our experimental results on nontrivial integer benchmarks show that SP-EPS can achieve as much as a geometric mean of 10 percent speedup over EPS when innermost loops are scheduled by SP-EPS, while it can achieve a geometric mean of 11.9 percent speedup when outer loops are also scheduled by SP-EPS.
3191125
Optimistic register coalescing
Graph-coloring register allocators eliminate copies by coalescing the source and target node of a copy if they do not interfere in the interference graph. Coalescing is, however, known to be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. Unlike aggressive coalescing which coalesces any pair of non-interfering copy-related nodes, conservative coalescing or iterated coalescing perform safe coalescing that preserves the colorability. Unfortunately, these heuristics give up coalescing too early, losing many opportunities of coalescing that would turn out to be safe. Moreover, they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. This paper proposes a new heuristic called optimistic coalescing which optimistically performs aggressive coalescing, thus fully exploiting the positive impact of coalescing, yet when a coalesced node is to be spilled, it is split back into separate nodes; there as a better chance of coloring one of them which reduces the overall spill cost.
37970940
Prefix-preserving IP address anonymization: measurement-based security evaluation and a new cryptography-based scheme
Real-world traffic traces are crucial for Internet research, but only a very small percentage of traces collected are made public. One major reason why traffic trace owners hesitate to make the traces publicly available is the concern that confidential and private information may be inferred from the trace. We focus on the problem of anonymizing IP addresses in a trace. More specifically, we are interested in prefix-preserving anonymization in which the prefix relationship among IP addresses is preserved in the anonymized trace, making such a trace usable in situations where prefix relationships are important. The goal of our work is two fold. First, we develop a cryptography-based, prefix-preserving anonymization technique that is provably as secure as the existing well-known TCPdpriv scheme, and unlike TCPdpriv, provides consistent prefix-preservation in large scale distributed setting. Second, we evaluate the security properties inherent in all prefix-preserving IP address anonymization schemes (including TCPdpriv). Through the analysis of Internet backbone traffic traces, we investigate the effect of some types of attacks on the security of any prefix-preserving anonymization algorithm. We also derive results for the optimum manner in which an attack should proceed, which provides a bound on the effectiveness of attacks in general.
1516306
Analysis of measured single-hop delay from an operational backbone network
We measure and analyze the single-hop packet delay through operational routers in a backbone IP network. First we present our delay measurements through a single router. Then we identify step-by-step the factors contributing to single-hop delay. In addition to packet processing, transmission, and queueing delays, we identify the presence of very large delays due to non-work-conserving router behavior. We use a simple output queue model to separate those delay components. Our step-by-step methodology used to ohtain the pure queueing delay is easily applicable to any single-hop delay measurements. After obtaining the queueing delay, we analyze the tail of its distribution, and find that it is long tailed and fits a Weihull distrihution with the scale parameter, a = 0.5, and the shape parameter, b = 0.58 to 0.6. The measured average queueing delay is larger than predicted by M/M/l, M/G/l, and FBM models when the link utilization is below 70%, but its absolute value is quite small.
11481277
On the correlation between route dynamics and routing loops
Routing loops are caused by inconsistencies in the routing state of the network. Although undesirable from this aspect, they can provide insight into the routing dynamics that caused them. In this work we present a methodology that utilizes a priori knowledge of loops to study the correlation between routing loops and routing events that could have caused them. We apply our technique to associate route changes with packet loops detected in actual traffic traces collected from the Sprint Backbone. Our study shows that a strong correlation exists between loops and changes in the BGP routing state while the link state protocols ISIS is seldom responsible for such events. Our analysis also identifies factors that influence the distribution of loop path lengths as well as the effectiveness of our detection techniques.
5965700
Analysis of topological characteristics of huge online social networking services
Social networking services are a fast-growing business in the Internet. However, it is unknown if online relationships and their growth patterns are the same as in real-life social networks. In this paper, we compare the structures of three online social networking services: Cyworld, MySpace, and orkut, each with more than 10 million users, respectively. We have access to complete data of Cyworld's ilchon (friend) relationships and analyze its degree distribution, clustering property, degree correlation, and evolution over time. We also use Cyworld data to evaluate the validity of snowball sampling method, which we use to crawl and obtain partial network topologies of MySpace and orkut. Cyworld, the oldest of the three, demonstrates a changing scaling behavior over time in degree distribution. The latest Cyworld data's degree distribution exhibits a multi-scaling behavior, while those of MySpace and orkut have simple scaling behaviors with different exponents. Very interestingly, each of the two e ponents corresponds to the different segments in Cyworld's degree distribution. Certain online social networking services encourage online activities that cannot be easily copied in real life; we show that they deviate from close-knit online social networks which show a similar degree correlation pattern to real-life social networks.
2527806
Knowledge representation for product design using Techspecs Concept Ontology
Sharing and reusing product design information can help reduce cost and time when developing new products and facilitate good product family design. An appropriate representation scheme for components and products is important to share and reuse this information effectively. The objective in this research is to develop a method for representing components and products using an ontology based on the Techspecs Concept Ontology (TCO), which consists of functionality, assembly, and product technical specifications. We use a device ontology for representing the behavior, functionality, and relationships of products and their components. This concept enables better understanding of the representation of the products and components and improves the process of searching for components satisfying customer needs and functional requirements. We demonstrate TCO development using a case study involving a family of power tools. Future work involving the use of TCO to capture semantics associated with components and products to represent knowledge for use with agents is also discussed.