An official website of the United States government
A sparsification of a given graph G is a sparser graph (typically a subgraph) which aims to approximate or preserve some property of G. Examples of sparsifications include but are not limited to spanning trees, Steiner trees, spanners, emulators, and distance preservers. Each vertex has the same priority in all of these problems. However, real-world graphs typically assign different “priorities” or “levels” to different vertices, in which higher-priority vertices require higher-quality connectivity between them. Multi-priority variants of the Steiner tree problem have been studied in prior literature but this generalization is much less studied for other sparsification problems. In this paper, we define a generalized multi-priority problem and present a rounding-up approach that can be used for a variety of graph sparsifications. Our analysis provides a systematic way to compute approximate solutions to multi-priority variants of a wide range of graph sparsification problems given access to a single-priority subroutine.
more »
« less
This content will become publicly available on January 1, 2026
Optimal Admission Policy in a Cloud Data Center with Priority and Non-Priority Tasks
More Like this
-
-
This paper studies a cloud datacenter (DC) consisting of two types of tasks with different priority levels. While non-priority tasks generally request the use of a single virtual machine (VM), priority tasks may utilize multiple available VMs to accelerate processing. We focus on determining whether to accept or reject non-priority tasks to maximize overall system benefits. By formulating the problem as a stochastic dynamic program, it is verified that the best approach for handling nonpriority tasks adheres to a control-limit framework. Both experimental outcomes and numerical evaluations highlight the efficacy of the proposed method, leading to the identification of the optimal threshold. The key contribution of this paper is the development of a stochastic dynamic program for DC resource management and the explicit derivation of an optimal control-limit policy. Both value iteration and linear programming methods are utilized to solve optimization problems. These results offer essential understanding for assessing the performance of various DC models, optimizing both rewards and resources efficiently.more » « less
-
Modern server workloads have large code footprints which are prone to front-end bottlenecks due to instruction cache capacity misses. Even with the aggressive fetch directed instruction prefetching (FDIP), implemented in modern processors, there are still significant front-end stalls due to I-Cache misses. A major portion of misses that occur on a BPU-predicted path are tolerated by FDIP without causing stalls. Prior work on instruction prefetching, however, has not been designed to work with FDIP processors. Their singular goal is reducing I-Cache misses, whereas FDIP processors are designed to tolerate them. Designing an instruction prefetcher that works in conjunction with FDIP requires identifying the fraction of cache misses that impact front-end performance (that are not fully hidden by FDIP), and only targeting them. In this paper, we propose Priority Directed Instruction Prefetching (PDIP), a novel instruction prefetching technique that complements FDIP by issuing prefetches for only targets where FDIP struggles - along the resteer path of front-end stall-causing events. PDIP identifies these targets and associates them with a trigger for future prefetch. At a 43.5KB budget, PDIP achieves up to 5.1% IPC speedup on important workloads such as cassandra and a geomean IPC speedup of 3.2% across 16 benchmarks.more » « less
