15509008
Exploring Small-Scale and Large-Scale CMP Architectures for Commercial Java Servers
As we enter the era of chip multiprocessor (CMP) architectures, it is important that we explore the scaling characteristics of mainstream server workloads on these platforms. In this paper, we analyze the performance of an Enterprise Java workload (SPECjbb2005) on two important classes of CMP architectures. One class of CMP platforms comprise of "small-scale" CMP (SCMP) processors with a few large out-of order cores on the die. Another class of CMP platforms comprise of "large-scale" CMP (LCMP) processors) with several small in-order cores on the die. For these classes of CMP architectures to succeed, it is important that there are sufficient resources (cache, memory and interconnect) to allow for a balanced scalable platform. In this paper, we focus on evaluating the resource scaling characteristics (cores, caches and memory) of SPECjbb2005 on these two architectures and understanding architectural trade-offs that may be required in future CMP offerings. The overall evaluation is uniquely conducted using four different methodologies (measurements on latest platforms, trace-based cache simulation, trace-based platform simulation and execution-driven emulation). Based on our findings, we summarize the architectural recommendations for future CMP server platforms (e.g. the need for large DRAM caches)
19000804
Receive Side Coalescing for Accelerating TCP/IP Processing
With rapid advancements in Ethernet technology, Ethernet speeds have increased by 10 fold, from 1 to 10Gbps, in a period of 2-3 years. This sudden increase in speeds has outpaced the rate at which processor and memory speeds have been increasing, raising concerns that TCP/IP processing will not scale to these levels. As a result, applications running on commercial servers will not be able to take advantage of the increased Ethernet bandwidth. This has led to a flurry of activity in the industry and academia focused on finding ways to scale up TCP/IP processing to 10Gbps and beyond. In this paper, we propose a novel technique called "Receive Side Coalescing" (RSC) that increases TCP/IP processing efficiencies significantly. RSC allows NICs to identify packets that belong to same TCP/IP flow and coalesce them into a single large packet. As a result, TCP/IP stack has to process fewer packets reducing per packet processing costs. NIC can do this coalescing of packets during interrupt moderation time hence packet latency is not affected. We have collected packet traces and analyzed those to find out how much coalescing is possible in different scenarios. Our analysis shows that about 50% reduction in number of packets is possible. We have prototyped RSC on Windows and Linux to understand the benefits, and the results show that 2-7% of savings in CPU utilization is possible at 1Gbps speeds. Projection models developed to estimate processing costs at 10Gbps show that RSC can save up to 20% of the CPU.
3098509
The nature of novelty detection
Sentence level novelty detection aims at spotting sentences with novel information from an ordered sentence list. In the task, sentences appearing later in the list with no new meanings are eliminated. For the task of novelty detection, the contributions of this paper are three-fold. First, conceptually, this paper reveals the computational nature of the task currently overlooked by the Novelty community—Novelty as a combination of partial overlap (PO) and complete overlap (CO) relations between sentences. We define partial overlap between two sentences as a sharing of common facts, while complete overlap is when one sentence covers all of the meanings of the other sentence. Second, technically, a novel approach, the selected pool method is provided which follows naturally from the PO-CO computational structure. We provide formal error analysis for selected pool and methods based on this PO-CO framework. We address the question how accurate must the PO judgments be to outperform the baseline pool method. Third, experimentally, results were presented for all the three novelty datasets currently available. Results show that the selected pool is significantly better or no worse than the current methods, an indication that the term overlap criterion for the PO judgments could be adequately accurate.
14270828
A Strict Approach to Approximating Lognormal Sum Distributions
In this paper, the least squares (LS) approximation approach is applied to solve the approximation problem of a sum of lognormal random variables (RV). The least squares curve fitting technique is first used to obtain the approximated closed-form pdf of the sum RV. The second time use of the least squares curve fitting technique brings the explicit closed-form expressions of the coefficients as a function of the number of the summands and the dB spread of the summands. Simulation results show that the proposed approximation exhibits a good match with the simulation results in the interested range of the distributions of the summands. Furthermore, errors due to a mixed use of the sum RV in the domain of the original variable and the domain of the logarithm are pointed out and the corrected results are presented
31340161
The Empirical Impact of the Nature of Novelty Detection
Novelty detection systems aim at reducing redundant documents or sentences from a list of documents chronologically ordered. In the task, sentences appearing later in the list with no new meanings are eliminated. In an accompanying paper, the nature of novelty detection was revealed – Novelty as a combination of the PO (partial overlap) and CO (complete overlap) relations, which can be treated as two classification tasks; theoretical impacts were given. This paper provides what the nature of the task mean empirically. One new method – selected pool – implementing the nature of the task gained improvements on TREC Novelty datasets. New evaluation criteria are given, which are natural from the viewpoint of the nature of novelty detection.
2050065
A Comparison of Sample-Path-Based Simulation-Optimization and Stochastic Decomposition for Multi-Location Transshipment Problems
Because of its applicability, as well as its generality, research in the area of simulation-optimization continues to attract significant attention. These methods, most of which rely on the statistically motivated search techniques, are at their best when very little is known about the structure of the function (e.g., function evaluations are treated as "blackbox" function-calls). In some applications such as the one discussed in this paper, objective function values may be obtained through linear/network flow optimization models. In such cases, the objective function may be convex, and in such circumstances, very large instances can be solved using stochastic programming techniques. This paper presents a computational case for using such techniques, whenever applicable
45415063
Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem
The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a (⌈Ds/2⌉ + 1)/(⌊log2(Ds + 1)⌋ + 1)-approximation algorithm for MVRST where Ds is the minimum diameter of spanning trees of G.