Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “maximum-flow”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

Wave function analysis with a maximum flow algorithm

An efficient algorithm for computing the maximum-flow path in a network is applied to the identification of the dominant configuration state functions (CSFs) in a graphically contracted function (GCF), configuration interaction, wave function. The flow network is a space of spin-adapted CSFs represented by a Shavitt graph, wherein the nodes correspond to orbital occupations and spin quantum numbers. The graph nodes are connected by arcs, and an arc density is defined as sums of the associated squared CSF coefficients. A max-min approach determines an upper bound to the maximum possible incoming flow for each graph node. A backtracking step generates a candidate walk and is followed by a limited search of alternative branching paths for the dominant CSF. The arc density contributions are removed from the graph, and the algorithm is reapplied to the updated graph. This list of generated walks can be partitioned in order to guarantee that the dominant CSFs have been identified. All of the steps in this algorithm are computationally efficient and do not depend on the potentially large dimension of the underlying linear CSF expansion space. An analysis of low-lying valence states of C-2 illustrates the method.

74 ATOMIC AND MOLECULAR PHYSICS↗

I/O load balancing for big data HPC applications

High Performance Computing (HPC) big data problems require efficient distributed storage systems. However, at scale, such storage systems often experience load imbalance and resource contention due to two factors: the bursty nature of scientific application I/O; and the complex I/O path that is without centralized arbitration and control. For example, the extant Lustre parallel file system-that supports many HPC centers-comprises numerous components connected via custom network topologies, and serves varying demands of a large number of users and applications. Consequently, some storage servers can be more loaded than others, which creates bottlenecks and reduces overall application I/O performance. Existing solutions typically focus on per application load balancing, and thus are not as effective given their lack of a global view of the system. In this paper, we propose a data-driven approach to load balance the I/O servers at scale, targeted at Lustre deployments. To this end, we design a global mapper on Lustre Metadata Server, which gathers runtime statistics from key storage components on the I/O path, and applies Markov chain modeling and a minimum-cost maximum-flow algorithm to decide where data should be placed. Evaluation using a realistic system simulator and a real setup shows that our approach yields better load balancing, which in turn can improve end-to-end performance.

Paul, Arnab K.↗

Identifying security checkpoints locations to protect the major U.S. urban areas

Transit networks are integral to the economy and to society, but at the same time they could allow terrorists to transport weapons of mass destruction into any city. Road networks are especially vulnerable, because they lack natural checkpoints unlike air networks that have security measures in place at all major airports. One approach to mitigate this risk is ensuring that every road route passes through at least one security checkpoint. Using the Ford-Fulkerson maximum-flow algorithm, we generate a minimum set of checkpoint locations within a ring-shaped buffer area surrounding the 50 largest US urban areas. We study how the number of checkpoints changes as we increase the buffer width to perform a cost-benefit analysis and to identify groups of cities that behave similarly. The set of required checkpoints is surprisingly small (10-124) despite the hundreds of thousands of road arcs in those areas, making it feasible to protect all major cities.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗