1748998
Minimum Register Instruction Scheduling: A New Approach for Dynamic Instruction Issue Processors
Modern superscalar architectures with dynamic scheduling and register renaming capabilities have introduced subtle but important changes into the tradeoffs between compile-time register allocation and instruction scheduling. In particular, it is perhaps not wise to increase the degree of parallelism of the static instruction schedule at the expense of excessive register pressure which may result in additional spill code. To the contrary, it may even be beneficial to reduce the register pressure at the expense of constraining the degree of parallelism of the static instruction schedule. This leads to the following interesting problem: given a data dependence graph (DDG) G, can we derive a schedule S for G that uses the least number of registers ? 
 
In this paper, we present a heuristic approach to compute the near-optimal number of registers required for a DDG G (under all possible legal schedules). We propose an extended list-scheduling algorithm which uses the above number of required registers as a guide to derive a schedule for G that uses as few registers as possible. Based on such an algorithm, an integrated approach for register allocation and instruction scheduling for modern superscalar architectures can be developed.
313172
Minimum register instruction sequence problem: revisiting optimal code generation for DAGs
We revisit the optimal code generation or evaluation order determination problem-the problem of generating an instruction sequence from a data dependence graph (DDG). In particular, we are interested in generating an instruction sequence S that is optimal in terms of the number of registers used by the sequence S. We call this MRIS (Minimum Register Instruction Sequence) problem. We developed an efficient heuristic solution for the MRIS problem based on the notion of instruction lineage. This solution facilitates the sharing of registers among instructions within a lineage and across lineages by exploiting the structure of a DDG. We implemented our solution on a production compiler and measured the reduction in the number of (spill) loads and (Spill) stores and the wall-clock execution time for the SPEC95 floating point benchmark suite. On average our method reduced the number of loads and stores by 11.5% and 15.9%, respectively, and decreased the total execution time by 2.5%.
14748826
QoS-Aware Optimization of Composite-Service Fulfillment Policy
In a service-oriented IT infrastructure, functional capabilities of a computing component are externalized via one or more service interfaces. Driven by the demand for business agility and return-on-investment optimization, various dynamic service discovery and composition technologies have been proposed and developed with a common goal of enabling business-aligned fulfillment of customer requests. However, from the viewpoint of capacity planning and IT optimization, much work is still needed in helping an enterprise decide the "optimal" IT resources necessary for deploying the atomic services in support of those composite ones. The service deployment decision must be integrated with the request fulfillment policy so that the differentiated quality-of-service (QoS) requirements of service requests can be met, for instance, with minimum hardware/software cost. In this paper, we propose an approach for QoS-aware optimization of composite-service fulfillment policy. Without loss of generality, we assume that the optimization goal is to minimize the number of machines subject to response time and throughput requirements. After presenting our approach to the optimization problem using the assumption, we show that an NP-hard throughput optimization problem must be attacked. We then illustrate how we attack the problem via an efficient heuristic algorithm. The algorithm decomposes the end-to-end response time requirement for each type of composite service into atomic-service level response time assurance, and co-locate atomic services with similar response time assurance on machines with similar utilization characteristics. The algorithm exemplifies an integrated approach to optimizing service deployment and service composition. We demonstrate that the algorithm achieves a substantially higher throughput than a common baseline algorithm.
3953733
TCP-Real: receiver-oriented congestion control
We introduce a receiver-oriented approach to congestion control, demonstrated by an experimental protocol, TCP-Real. The protocol allows for a measurement-based transmission strategy, which complements the "blind" increase/ decrease window adjustments. Owing to its design, the protocol displays an inherent property to produce comprehensive dynamics in heterogeneous environments with wired or wireless networks and delay-sensitive or -tolerant applications. TCP-Real controls congestion as standard TCP does. However, its receiver-oriented nature and its "wave" communication pattern allow for two amending mechanisms: (i) congestion avoidance, which reduces unnecessary transmission gaps that hurt the performance of time-constrained applications, and (ii) advanced error detection and classification, which designates recovery tactics responsive to the nature of the errors, thereby enhancing the protocol performance over wireless links or asymmetric paths.We detail the protocol mechanisms and specification and we report extensively on the comparative fairness and efficiency evaluation of standard TCP, TCP-Real, and TCP-friendly protocols for both delay-tolerant and -sensitive applications and in both wired and wireless networks.
36530209
Determination of the star valency of a graph
The star valency of a graph G is the minimum, over all star decompositions π, of the maximum number of elements in π incident with a vertex. The maximum average degree of G, denoted by dmax-ave(G), is the maximum average degree of all subgraphs of G. In this paper, we prove that the star valency of G is either ⌈dmax-ave(G)/2⌉ or ⌈dmax-ave(G)/2⌉ + 1, and provide a polynomial time algorithm for determining the star valency of a graph.
12113641
Neighbor number, valley seeking and clustering
This paper proposes a novel nonparametric clustering algorithm capable of identifying shape-free clusters. This algorithm is based on a nonparametric estimation of the normalized density derivative (NDD) and the local convexity of the density distribution function, both of which are represented in a very concise form in terms of neighbor numbers. We use NDD to measure the dissimilarity between each pair of observations in a local neighborhood and to build a connectivity graph. Combined with the local convexity, this similarity measure can detect observations in local minima (valleys) of the density function, which separate observations in different major clusters. We demonstrate that this algorithm has a close relationship with the single-linkage hierarchical clustering and can be viewed as its extension. The performance of the algorithm is tested with both synthetic and real datasets. An example of color image segmentation is also given. Comparisons with several representative existing algorithms show that the proposed method can robustly identify major clusters even when there are complex configurations and/or large overlaps.
11462933
On flows in bidirected graphs
Bouchet conjectured that every bidirected graph which admits a nowhere-zero bidirected flow will admit a nowhere-zero bidirected 6-flow [A. Bouchet, Nowhere-zero integer flows on a bidirected graph, J. Combin. Theory Ser. B 34 (1983) 279-292]. He proved that this conjecture is true with 6 replaced by 216. Zyka proved in his Ph.D dissertation that it is true with 6 replaced by 30. Khelladi proved it is true with 6 replaced with 18 for 4-connected graphs [A. Khelladi, Nowhere-zero integer chains and flows in bidirected graphs, J. Combin. Theory Ser. B 43 (1987) 95-115]. In this paper, we prove that Bouchet's conjecture is true for 6-edge connected bidirected graphs.