An official website of the United States government
Simulating storage cache hierarchies enables effi- cient exploration of their configuration space, including diverse topologies, parameters and policies, and devices with varied performance characteristics, while avoiding expensive physical experiments. Miss Ratio Curves (MRCs) efficiently characterize the performance of a cache over a range of cache sizes. These useful tools reveal “key points” for cache simulation, such as knees in the curve that immediately follow sharp cliffs. Unfortunately, there are no automated techniques for efficiently finding key points in MRCs, and the cross-application of existing knee-detection algorithms yields inaccurate results. We present a multi-stage framework that identifies key points in any MRC, for both stack-based (e.g., LRU) and more sophisticated eviction algorithms (e.g., ARC). Our approach quickly locates candidates using efficient hash-based sampling, curve simplification, knee detection, and novel post-processing filters. We introduce Z-Method, a new multi-knee detection algorithm that employs statistical outlier detection to choose promising points robustly and efficiently. We evaluate our framework against seven other knee-detection algorithms, using both ARC and LRU MRCs from 106 diverse real-world workloads, and apply it to identify key points in multi-tier MRCs. Compared to naïve approaches, our framework reduces the total number of points needed to accurately identify the best two-tier cache hierarchies by an average factor of approximately 5.5x for ARC and 7.7x for LRU.
more »
« less
This content will become publicly available on May 1, 2026
Kneeliverse: A universal knee-detection library for performance curves
Identifying knee and elbow points in performance curves is a critical task in various domains, including machine learning and system design. These points represent optimal trade-offs between cost and performance, facilitating efficient decision-making and resource allocation. However, accurately determining the knees and elbows in curves poses a significant challenge. To address this challenge, we introduce Kneeliverse, an open-source library dedicated to knee/elbow point detection. Kneeliverse incorporates a suite of well-established knee-detection algorithms, including Menger, L-method, Kneedle, and DFDT. Additionally, Kneeliverse extends these algorithms to detect multiple knees and elbows in complex curves, employing a recursive approach. Kneeliverse further includes Z-Method, a recently developed algorithm specifically designed for multi-knee detection.
more »
« less
- PAR ID:
- 10633458
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- SoftwareX
- Volume:
- 30
- Issue:
- C
- ISSN:
- 2352-7110
- Page Range / eLocation ID:
- 102161
- Subject(s) / Keyword(s):
- Knee estimation Multi-knee estimation Optimization Python
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Storage cache hierarchies include diverse topologies, assorted parameters and policies, and devices with varied performance characteristics. Simulation enables efficient exploration of their configuration space while avoiding expensive physical experiments. Miss Ratio Curves (MRCs) efficiently characterize the performance of a cache over a range of cache sizes, revealing ‘‘key points’’ for cache simulation, such as knees in the curve that immediately follow sharp cliffs. Unfortunately, there are no automated techniques for efficiently finding key points in MRCs, and the cross-application of existing knee-detection algorithms yields inaccurate results. We present a multi-stage framework that identifies key points in any MRC, for both stack- based (e.g., LRU) and more sophisticated eviction algorithms (e.g., ARC). Our approach quickly locates candidates using efficient hash-based sampling, curve simplification, knee detection, and novel post-processing filters. We introduce Z-Method, a new multi-knee detection algorithm that employs statistical outlier detection to choose promising points robustly and efficiently. We evaluated our framework against seven other knee-detection algorithms, identifying key points in multi-tier MRCs with both ARC and LRU policies for 106 diverse real-world workloads. Compared to naïve approaches, our framework reduced the total number of points needed to accurately identify the best two-tier cache hierarchies by an average factor of approximately 5.5x for ARC and 7.7x for LRU. We also show how our framework can be used to seed the initial population for evolutionary algorithms. We ran 32,616 experiments requiring over three million cache simulations, on 151 samples, from three datasets, using a diverse set of population initialization techniques, evolutionary algorithms, knee-detection algorithms, cache replacement algorithms, and stopping criteria. Our results showed an overall acceleration rate of 34% across all configurations.more » « less
-
Abstract While woody root structures, such as bald cypress (Taxodium distichum) “knees,” can act as conduits of methane (CH4), little has been done to explain variation from this flux pathway. We captured spatial (i.e., across knee surface, within sites, between sites) and temporal dynamics of CH4from knees, and built empirical models to predict the contribution of knees to net CH4fluxes. Knee and soil CH4fluxes were measured across seasons within the lower Mississippi Alluvial Valley in a main channel (semi‐permanently flooded), side channel (seasonally flooded), and a reservoir edge (artificially flooded). Knees were a net source of CH4across all seasons, even during periods of soil CH4uptake. During periods of high knee CH4efflux, fluxes varied across the knee surface, decreasing with height from the ground. Knee CH4fluxes at the main and side channels decreased during a severe drought and increased ∼ ten‐fold in summer and two‐fold in winter following flooding events. At the reservoir edge, knee fluxes differed between the controlled draw up and draw down at the same water level, likely due to differences in temperature and oxygen availability. Knee CH4fluxes were positively correlated with water level (measured from subsurface wells, above ∼−70 cm in the soil profile) and subsurface temperature, but the strength of the relationships differed across geomorphic positions. Cypress knees appear to be an important contributor to wetland CH4efflux and accounting for the density of knees is needed to upscale their fluxes and better understand their ecosystem contribution.more » « less
-
Shaharudin, Shazlin (Ed.)Objective To apply biclustering, a methodology originally developed for analysis of gene expression data, to simultaneously cluster observations and clinical features to explore candidate phenotypes of knee osteoarthritis (KOA) for the first time. Methods Data from the baseline Osteoarthritis Initiative (OAI) visit were cleaned, transformed, and standardized as indicated (leaving 6461 knees with 86 features). Biclustering produced submatrices of the overall data matrix, representing similar observations across a subset of variables. Statistical validation was determined using the novel SigClust procedure. After identifying biclusters, relationships with key outcome measures were assessed, including progression of radiographic KOA, total knee arthroplasty, loss of joint space width, and worsening Western Ontario and McMaster Universities Osteoarthritis Index (WOMAC) scores, over 96 months of follow-up. Results The final analytic set included 6461 knees from 3330 individuals (mean age 61 years, mean body mass index 28 kg/m 2 , 57% women and 86% White). We identified 6 mutually exclusive biclusters characterized by different feature profiles at baseline, particularly related to symptoms and function. Biclusters represented overall better (#1), similar (#2, 3, 6), and poorer (#4, 5) prognosis compared to the overall cohort of knees, respectively. In general, knees in biclusters #4 and 5 had more structural progression (based on Kellgren-Lawrence grade, total knee arthroplasty, and loss of joint space width) but tended to have an improvement in WOMAC pain scores over time. In contrast, knees in bicluster #1 had less incident and progressive KOA, fewer total knee arthroplasties, less loss of joint space width, and stable pain scores compared with the overall cohort. Significance We identified six biclusters within the baseline OAI dataset which have varying relationships with key outcomes in KOA. Such biclusters represent potential phenotypes within the larger cohort and may suggest subgroups at greater or lesser risk of progression over time.more » « less
-
Abstract We compared the ability of seven machine learning algorithms to use wearable inertial measurement unit (IMU) data to identify the severe knee loading cycles known to induce microdamage associated with anterior cruciate ligament rupture. Sixteen cadaveric knee specimens, dissected free of skin and muscle, were mounted in a rig simulating standardized jump landings. One IMU was located above and the other below the knee, the applied three-dimensional action and reaction loads were measured via six-axis load cells, and the three-dimensional knee kinematics were also recorded by a laboratory motion capture system. Machine learning algorithms were used to predict the knee moments and the tibial and femur vertical forces; 13 knees were utilized for training each model, while three were used for testing its accuracy (i.e., normalized root-mean-square error) and reliability (Bland–Altman limits of agreement). The results showed the models predicted force and knee moment values with acceptable levels of error and, although several models exhibited some form of bias, acceptable reliability. Further research will be needed to determine whether these types of models can be modified to attenuate the inevitable in vivo soft tissue motion artifact associated with highly dynamic activities like jump landings.more » « less
