Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “pipeline”

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.

At least 757 records · Page 42

BRAKER3: Fully automated genome annotation using RNA-seq and protein evidence with GeneMark-ETP, AUGUSTUS, and TSEBRA

Gene prediction has remained an active area of bioinformatics research for a long time. Still, gene prediction in large eukaryotic genomes presents a challenge that must be addressed by new algorithms. The amount and significance of the evidence available from transcriptomes and proteomes vary across genomes, between genes, and even along a single gene. User-friendly and accurate annotation pipelines that can cope with such data heterogeneity are needed. The previously developed annotation pipelines BRAKER1 and BRAKER2 use RNA-seq or protein data, respectively, but not both. A further significant performance improvement integrating all three data types was made by the recently released GeneMark-ETP. We here present the BRAKER3 pipeline that builds on GeneMark-ETP and AUGUSTUS, and further improves accuracy using the TSEBRA combiner. BRAKER3 annotates protein-coding genes in eukaryotic genomes using both short-read RNA-seq and a large protein database, along with statistical models learned iteratively and specifically for the target genome. We benchmarked the new pipeline on genomes of 11 species under an assumed level of relatedness of the target species proteome to available proteomes. BRAKER3 outperforms BRAKER1 and BRAKER2. The average transcript-level F1-score is increased by about 20 percentage points on average, whereas the difference is most pronounced for species with large and complex genomes. BRAKER3 also outperforms other existing tools, MAKER2, Funannotate, and FINDER. The code of BRAKER3 is available on GitHub and as a ready-to-run Docker container for execution with Docker or Singularity. Overall, BRAKER3 is an accurate, easy-to-use tool for eukaryotic genome annotation.

59 BASIC BIOLOGICAL SCIENCES↗

High-Performance Deep Learning Toolbox for Genome-Scale Prediction of Protein Structure and Function

Computational biology is one of many scientific disciplines ripe for innovation and acceleration with the advent of high-performance computing (HPC). In recent years, the field of machine learning has also seen significant benefits from adopting HPC practices. In this work, we present a novel HPC pipeline that incorporates various machine-learning approaches for structure-based functional annotation of proteins on the scale of whole genomes. Our pipeline makes extensive use of deep learning and provides computational insights into best practices for training advanced deep-learning models for high-throughput data such as proteomics data. We showcase methodologies our pipeline currently supports and detail future tasks for our pipeline to envelop, including large-scale sequence comparison using SAdLSA and prediction of protein tertiary structures using AlphaFold2.

Gao, Mu↗

CONSTRAINT-INDEPENDENT CONSTANT CTOA DETERMINATION FOR DUCTILE STABLE CRACK GROWTH

Crack tip opening angle (CTOA) has been used as a reliable fracture toughness parameter for decades to characterize stable ductile crack growth for thin-walled aerospace structures in the low-constraint conditions. Recently, the CTOA parameter was also applied to the pipeline industry, and a CTOA test standard ASTM E3039 was thus developed for testing a critical constant CTOA. Research showed that the constant CTOA can reasonably describe fracture toughness required to arrest a dynamic crack propagation for a modern gas pipeline. However, the CTOA fracture criterion requires constraint-independent CTOA toughness against stable ductile crack growth. ASTM E3039 recommends a drop weight tearing test (DWTT) specimen for CTOA testing. Since a shallow crack is used, DWTT measured CTOA may depend on constraint level at the crack tip. To understand if it is the case, this paper evaluates the critical CTOA for a set of fracture toughness tests on single edge notched bend (SENB) specimens with shallow and deep cracks based on four CTOA estimation models. In which, the Ln(P)-LLD linear fit model is similar to that used by ASTM E3039 in the CTOA calculation. Fracture test data for X80 pipeline steel and HY80 structural steel are considered in the CTOA evaluation. The results show that the four CTOA models can determine a crack size-independent constant CTOA over stable ductile crack growth for the SENB specimens. As a result, CTOA determined by ASTM E3039 is constraintindependent and transferable to use for an actual crack propagating in a gas pipeline.

Zhu, Xian-Kui↗

EXPERIMENTAL VALIDATION OF THEORETICAL BURST STRENGTH SOLUTION FOR DEFECT-FREE THICK-WALLED PIPES

The burst pressure of line pipes is an important strength property required in pipeline design and integrity management. Historically, the Barlow formula in conjunction with the ultimate tensile stress (UTS) of pipeline steels were utilized to estimate the burst strength of line pipes. However, the Barlow formula did not consider the plastic flow effect for ductile steels and is applicable only to thin-walled pipes. In 2006, the present author proposed a new multiaxial plastic yield theory and obtained a theoretical Zhu-Leis solution of burst strength for defect-free thin-walled pipes in term of UTS and strain hardening exponent n of pipeline steels. The Zhu-Leis solution has been validated by various burst test data for thin-walled pipelines for a wide range of steel grades from Grade B to X120. Recently, the present author extended the Zhu-Leis theory of plasticity to thick-walled pipes and obtained the Zhu-Leis solution of burst pressure for thick-walled pipes. The proposed burst pressure solution is applicable to both thin and thick-walled pipes. To experimentally validate the proposed theoretical burst pressure solution, this paper obtains a set of burst test data for three thick-walled pipes in Grade B carbon steel with a nominal diameter of 2.375 inches and three nominal wall thicknesses, resulting in D/t = 15.4, 10.9, 6.9. Through comparisons, these burst data validate the theoretical burst pressure solution for thick-walled pipes. Moreover, two additional burst test datasets collected from literature for thin and thick-walled pipes further validate the proposed burst pressure solution for both thin and thick-walled pipes.

Zhu, Xiankui↗

Real-Time Highly Resolved Spatial-Temporal Vehicle Energy Consumption Estimation Using Machine Learning and Probe Data

Real-time highly resolved spatial-temporal vehicle energy consumption is a key missing dimension in transportation data. Most roadway link-level vehicle energy consumption data are estimated using average annual daily traffic measures derived from the Highway Performance Monitoring System; however, this method does not reflect day-to-day energy consumption fluctuations. As transportation planners and operators are becoming more environmentally attentive, they need accurate real-time link-level vehicle energy consumption data to assess energy and emissions; to incentivize energy-efficient routing; and to estimate energy impact caused by congestion, major events, and severe weather. This paper presents a computational workflow to automate the estimation of time-resolved vehicle energy consumption for each link in a road network of interest using vehicle probe speed and count data in conjunction with machine learning methods in real time. The real-time pipeline can deliver energy estimates within a couple seconds on query to its interface. The proposed method was evaluated on the transportation network of the metropolitan area of Chattanooga, Tennessee. The volume estimation results were validated with ground truth traffic volume data collected in the field. To demonstrate the effectiveness of the proposed method, the energy consumption pipeline was applied to real-world data to quantify road transportation-related energy reduction because of mitigation policies to slow the spread of COVID-19 and to measure energy loss resulting from congestion.

Severino, Joseph↗

Learning epistatic polygenic phenotypes with Boolean interactions

Detecting epistatic drivers of human phenotypes is a considerable challenge. Traditional approaches use regression to sequentially test multiplicative interaction terms involving pairs of genetic variants. For higher-order interactions and genome-wide large-scale data, this strategy is computationally intractable. Moreover, multiplicative terms used in regression modeling may not capture the form of biological interactions. Building on the Predictability, Computability, Stability (PCS) framework, we introduce the epiTree pipeline to extract higher-order interactions from genomic data using tree-based models. The epiTree pipeline first selects a set of variants derived from tissue-specific estimates of gene expression. Next, it uses iterative random forests (iRF) to search training data for candidate Boolean interactions (pairwise and higher-order). We derive significance tests for interactions, based on a stabilized likelihood ratio test, by simulating Boolean tree-structured null (no epistasis) and alternative (epistasis) distributions on hold-out test data. Finally, our pipeline computes PCS epistasis p-values that probabilisticly quantify improvement in prediction accuracy via bootstrap sampling on the test set. We validate the epiTree pipeline in two case studies using data from the UK Biobank: predicting red hair and multiple sclerosis (MS). In the case of predicting red hair, epiTree recovers known epistatic interactions surrounding MC1R and novel interactions, representing non-linearities not captured by logistic regression models. In the case of predicting MS, a more complex phenotype than red hair, epiTree rankings prioritize novel interactions surrounding HLA-DRB1 , a variant previously associated with MS in several populations. Taken together, these results highlight the potential for epiTree rankings to help reduce the design space for follow up experiments.

59 BASIC BIOLOGICAL SCIENCES↗

NETL Plastic Pipes Project - June 2022 Progress Report

Plastic or composite pipelines have been the bane of the utility locating industry because conduits are neither conductive nor magnetic, which are the properties traditionally used to locate buried utilities. Ground penetrating radar (GPR) is an effective geophysical tool for locating plastic/composite pipeline where the resistive cover allows for adequate penetration of radar energy. However, GPR cannot be used in areas where the soil cover is conductive due to significant clay and/or salt content. This study takes a comprehensive look at near-surface geophysical methods that potentially are useful for locating buried plastic/composite pipelines, either singly or in combination with other geophysical methods. Specifically, this modeling study uses computational numerical methods to forward model the response of GPR, resistivity, seismic, and gravity gradiometry methods to plastic/composite pipelines for various scenarios including: (1) pipe diameters ranging between 2 in. to 12 in.; (2) burial depths ranging between 3 ft to 4 ft; (3) various degrees in contrast in physical properties (i.e., permittivity, elasticity, electrical resistivity, density); and (4) various experimental acquisition choices (e.g., GPR radar frequencies, seismic source frequency, electrode spacing).

47 OTHER INSTRUMENTATION↗

Feature Extraction: Improving Remote Sensor Classification of Non-Proliferation

This research focuses on developing algorithms for nuclear non-proliferation detection using remote sensor modeling. To improve the performance of classification models, we implemented a data pipeline with feature extraction. This pipeline takes raw data and transforms it into smaller data points called features that still describe the model. Improving this classification works towards the departments of energy’s missions of ensuring American’s security and prosperity by creating technology that addresses nuclear challenges. To conduct this analysis, we used the Python programming language and some key packages, including tsfresh and TSFEL. Originally tsfresh was selected because it has the most statistical features out of all the packages. Later TSFEL was incorporated due to the additional features it can extract from data, such as temporal and spectral. However, feature extraction becomes challenging in the presence of missing values. In this case, two additional Python packages were added to our workflow, NumPy and pandas, allowing for the feature extraction process to handle unknown values. Our data pipeline was tested on data collected from a simulation that describes the process state of a physical example. The results show the pipeline’s capability to consume and extract a total 17 features from tabular data. Future work includes producing classifications using decision tree-based models such as XGBoost and improving data collection by analyzing feature importance.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Carbon Capture, Transport, And Storage (CTS) Cost Modeling Of The Onshore Gulf Coast

The onshore Gulf of Mexico region presents significant opportunities for CO2 capture, transport, and storage due to its numerous CO2 sources, such as power plants, refineries, and its substantial CO2 storage potential. However, operators face critical decisions in designing an efficient and cost-effective CO2 pipeline network. This study examines the economic implications of two primary strategies: constructing a trunkline with excess initial capacity versus developing dedicated pipelines incrementally as new CO2 sources come online. Building a trunkline first offers the advantage of future-proofing the network, allowing for the accommodation of increased CO2 volumes from various sources over time. However, this approach incurs higher upfront costs and risks underutilizing the transport capacity in the initial stages, potentially resulting in economic inefficiencies. Conversely, constructing dedicated pipelines for each new CO2 source as it becomes operational may avoid the initial overcapacity issue but fails to capitalize on the economies of scale. This could lead to higher overall costs due to the duplication of infrastructure and increased complexity in network management. This research employs a comprehensive cost-benefit analysis, integrating factors such as capital expenditure, operational costs, projected CO2 volumes, and potential economies of scale. Through this analysis, we aim to provide operators with insights into the most economically viable strategy for CO2 pipeline network design in the region. The findings underscore the importance of strategic planning and highlight the trade-offs between immediate capacity utilization and long-term cost savings, ultimately guiding stakeholders towards informed decision-making in the development of CO2 transport infrastructure. Presented at the 41st USAEE/IAEE North American Conference, 3-6 November 2024, Baton Rouge, LA, United States.

Shih, Chung Yan↗

OPEN-Augmented Reality GUI for Bioenergy Crop Phenotyping and Precision Agriculture (Donald Danforth Plant Science Center Final Scientific Technical Report)

The project led by the Donald Danforth Plant Science Center, in collaboration with Arizona State University, George Washington University, and Saint Louis University, has made significant strides in advancing the phenotypic analysis of bioenergy crops through the development of an innovative AI processing pipeline. This initiative was primarily funded by ARPA-E, with additional cost-sharing provided by the participating institutions. The project successfully utilized a variety of sensors—3D scanners, thermal, RGB, and hyperspectral—to refine algorithms for data-driven trait signature identification and improve the classification and visualization of plant traits. The developed AI processing pipeline is capable of handling the complex, multidimensional data characteristic of dynamic agricultural environments. 1) Contributions to understanding: The research has advanced the field of plant phenomics by showcasing the synergistic use of various sensor data to enhance the precision of trait analysis in bioenergy crops. Through the integration of 3D scanners, thermal, RGB, and hyperspectral sensors, the project has developed robust data-driven trait signature algorithms and visualization techniques. These innovations have facilitated detailed monitoring and management of plant traits, providing vital insights into plant growth dynamics and stress responses. Further, the project has broadened our understanding of how machine learning can be effectively applied in multi-sensor environments to refine trait analysis. By leveraging diverse datasets, the research has not only improved the accuracy of phenotypic assessments but also established a versatile methodological framework that can be extended beyond agriculture to other fields requiring detailed phenotypic analysis. 2) Technical effectiveness and economic feasibility: The AI processing pipeline developed in this project demonstrated significant technical effectiveness, achieving high throughput analysis of extensive phenotypic data and meeting targeted accuracies. This system exemplified the capability of advanced machine learning technologies to efficiently manage and analyze large, complex datasets. Economically, the implementation of the project-developed pipelines may offer substantial cost savings across multiple sectors. It enhances data analysis processes and significantly reduces the need for manual data interpretation, thereby decreasing both the time and resources required. 3) Public benefit: The project has significantly broadened the scope of agricultural methodologies to enhance phenotypic analysis, with potential applications in various sectors beyond agriculture. Additionally, the initiative fostered an enriching educational and collaborative environment, significantly enhancing the technical skills of participants. It also made substantial contributions to the scientific community by providing open-access data sets and tools, encouraging ongoing research and development across various disciplines. Overall, the project not only met its scientific goals but also showcased the extensive utility of integrating advanced machine learning and sensor data analysis technologies. These advancements have proven instrumental in driving forward both theoretical research and practical applications, setting a strong foundation for future explorations and innovations in data-driven science.

60 APPLIED LIFE SCIENCES↗

Core Model Proposal #350: Detailed Natural Gas Trade

This core model proposal adds detail to GCAM's natural gas trade model by separating gas trade between Liquefied Natural Gas (LNG) and six regional gas pipeline networks. This entails creating new trade markets for global LNG and the six regional pipeline networks, and modifying the regional natural gas sector in each region to reflect the competition between LNG and pipelines within imported natural gas, and between different pipeline networks. The nesting subsector capability (CMP #299 Infinite Subsector Nesting) was used to represent this additional level of competition on the consumption side.

03 NATURAL GAS↗

A Semi-Supervised Learning Method for the Identification of Bad Exposures in Large Imaging Surveys

As the data volume of astronomical imaging surveys rapidly increases, traditional methods for image anomaly detection, such as visual inspection by human experts, are becoming impractical. We introduce a machine-learning-based approach to detect poor-quality exposures in large imaging surveys, with a focus on the DECam Legacy Survey (DECaLS) in regions of low extinction (i.e., E ( B − V ) < 0.04 ). Our semi-supervised pipeline integrates a vision transformer (ViT), trained via self-supervised learning (SSL), with a k-Nearest Neighbor (kNN) classifier. We train and validate our pipeline using a small set of labeled exposures observed by surveys with the Dark Energy Camera (DECam). A clustering-space analysis of where our pipeline places images labeled in good and bad categories suggests that our approach can efficiently and accurately determine the quality of exposures. Applied to new imaging being reduced for DECaLS Data Release 11, our pipeline identifies 780 problematic exposures, which we subsequently verify through visual inspection. Being highly efficient and adaptable, our method offers a scalable solution for quality control in other large imaging surveys.

Luo, Yufeng (ORCID:0000000246230683)↗

Transport Cost for Carbon Removal Projects With Biomass and CO2 Storage

Strategies to remove carbon from the atmosphere are needed to meet global climate goals. Promising strategies include the conversion of waste biomass to hydrogen, methane, liquid fuels, or electricity coupled with CO 2 capture and storage (CCS). A key challenge for these projects is the need to connect geographically dispersed biomass supplies with geologic storage sites by either transporting biomass or CO 2 . We assess the cost of transport for biomass conversion projects with CCS using publicly available cost data for trucking, rail, and CO 2 pipelines in the United States. We find that for large projects (order of 1 Mt/yr CO 2 or greater), CO 2 by pipeline is the lowest cost option. However, for projects that send most of the biomass carbon to storage, such as gasification to hydrogen or electricity production, biomass by rail is a competitive option. For smaller projects and lower fractions of carbon sent to storage, such as for pyrolysis to liquid fuels, CO 2 by rail is the lowest cost option. Assessing three plausible example projects in the United States, we estimate that total transport costs range from $24/t-CO 2 stored for a gasification to hydrogen project traversing 670 km to $\$ 36$/t for a gasification to renewable natural gas project traversing 530 km. In general, if developers have flexibility in choosing transport mode and project type, biomass sources and storage sites can be connected across hundreds of kilometers for transport costs in the range of $20-40/t-CO 2 stored. Truck and rail are often viable modes when pipelines cannot be constructed. Distances of 1,000 km or more can be connected in the same cost range when shared CO 2 pipelines are employed.

09 BIOMASS FUELS↗

Deep Learning and Photogrammetric Reconstruction for Automated Crack Detection and Dimensional Measurement in Mining Operations

Surface crack detection and dimensional measurement at active mining sites present significant safety and operational challenges. Manual inspection methods are labor-intensive, spatially incomplete, and expose personnel to hazardous environments, while existing automated approaches have been developed primarily for concrete civil infrastructure and have not been validated on the complex, variable surfaces characteristic of mining environments. This dissertation presents an automated pipeline that integrates deep learning semantic segmentation with Structure-from-Motion photogrammetry to detect surface cracks and measure their aperture, length, and vertical displacement from standard RGB imagery acquired during routine Uncrewed Aerial Vehicle (UAV) survey operations, without requiring additional sensor hardware or manual measurement. The pipeline combines a U-Net architecture with an EfficientNet-B0 encoder, pretrained on the SDNET2018 concrete crack dataset and fine-tuned on a mining-specific dataset spanning laboratory concrete specimens, coal refuse impoundment embankments, and post-blast limestone quarry benches. Photogrammetric reconstruction is performed using COLMAP Structure-from-Motion and Multi-View Stereo, with crack segmentation masks projected into the reconstructed point cloud to enable three-dimensional vertical displacement measurement through local plane fitting and bimodal surface detection. The pipeline was validated across 36 controlled laboratory specimens at three imaging distances and four vertical displacement levels, achieving aperture measurement RMSE of 0.047 cm and R² of 0.954, and vertical displacement RMSE of 0.140 cm and R² of 0.966, against independent caliper measurements. Field application at a coal refuse impoundment in southwestern Pennsylvania detected 71 crack components across the embankment crest, with a dominant longitudinal crack exhibiting aperture values reaching 28 cm and a 95th percentile vertical displacement of 35.53 cm, consistent in magnitude and spatial distribution with simultaneously acquired LiDAR-derived estimates. Application across four post-blast limestone quarry bench datasets in California successfully characterized blast-induced fracture networks at ground sampling distances ranging from 0.59 to 1.23 cm/pixel, with detected crack geometries physically consistent with observable surface conditions at each site. The results demonstrate that deep learning-based crack detection and photogrammetric measurement can be integrated into routine UAV inspection workflows at mining sites, providing repeatable, scalable, and quantitative crack characterization across surface types, crack scales, and displacement magnitudes not previously addressed in the literature. The pipeline requires no dedicated surveying equipment beyond the UAV platforms already deployed at mine sites for survey and monitoring purposes, supporting practical adoption within existing operational workflows.

Crack detection, Dimensional Measurement↗

Retrospective Search for Strongly Lensed Supernovae in the DESI Legacy Imaging Surveys

The introduction of deep wide-field surveys in recent years and the adoption of machine-learning techniques have led to the discoveries of $\mathcal{O}$(10 4 ) strong gravitational lensing systems and candidates. However, the discovery of multiply-lensed transients remains a rarity. Lensed transients and especially lensed supernovae are invaluable tools to cosmology because they allow us to constrain cosmological parameters via lens modeling and the measurements of their time delays. In this paper, we develop a pipeline to perform a targeted lensed transient search. We apply this pipeline to 5807 strong lenses and candidates, which were identified in the literature, in the DESI Legacy Imaging Surveys Data Release 9 (DR9) footprint. For each system, we analyze every exposure in all of the observed bands (DECam g, r, and z). Our pipeline finds, groups, and ranks detections that are in sufficient proximity temporally and spatially. After the first round of inspection, for promising candidate systems, we further examine the newly available DR10 data (with additional i and Y bands). Here we present our targeted lensed supernova search pipeline and seven new lensed supernova candidates, including a very likely lensed supernova—probably a Type Ia—in a system with an Einstein radius of ~1$^{"}_{.}$5.

79 ASTRONOMY AND ASTROPHYSICS↗

Enabling Early Transient Discovery in LSST via Difference Imaging with DECam

We present SLIDE, a pipeline that enables transient discovery in data from the Vera C. Rubin Observatory’s Legacy Survey of Space and Time (LSST), using archival images from the Dark Energy Camera as templates for difference imaging. We apply this pipeline to the recently released Data Preview 1 (DP1; the first public release of Rubin commissioning data) and search for transients in the resulting difference images. The image subtraction, photometry extraction, and transient detection are all performed on the Rubin Science Platform. We demonstrate that SLIDE effectively extracts clean photometry by circumventing poor or missing LSST templates. We identified 29 previously unreported transients, 12 of which would not have been detected based on the DP1 DiaObject catalog. SLIDE will be especially useful for transient analysis in the early years of LSST, when template coverage will be largely incomplete or when templates may be contaminated by transients present at the time of acquisition. We present multiband light curves for a sample of known transients, along with new transient candidates identified through our search. Finally, we discuss the prospects of applying this pipeline during the main LSST survey. Our pipeline is broadly applicable and will support studies of all transients with slowly evolving phases.

Dong, Yize 一泽董 [Harvard-Smithsonian Center for Ast↗

Helium recovery system at IB3A

The growing demand for sustainable cryogenic operations at Fermilab has underscored the need to improve helium management, particularly at the Industrial Building 3A (IB3A) test facility. IB3A characterizes and tests superconductors, cables, and coils for projects such as the HL-LHC AUP and Mu2e, yet currently relies on 500 L Dewars whose boil-off is vented to atmosphere, wasting a critical, non-renewable resource and increasing the cost of testing. A project is therefore under way to link IB3A to an existing purification and liquefaction station in a neighboring building through a dedicated pipeline. Captured helium will be transferred, purified, reliquefied, and returned for reuse, cutting losses and operating costs. This paper details the first two project phases: "Design and Engineering" and "Procurement and Installation." The design phase finalizes pipeline specifications, establishes flow-control requirements, and resolves integration challenges with existing cryogenic infrastructure. The procurement and installation phase covers material sourcing, pipeline construction, and deployment of control and monitoring systems to assure reliable, efficient operation. Key technical hurdles-route optimization, pressure drop mitigation, and interface compatibility-are discussed alongside implemented solutions. Implementing the pipeline and upgrading IB3A will dramatically reduce helium consumption and therefore testing cost, strengthening Fermilab's capacity to support frontier science far into the future.

Porwisiak, D. [Fermilab; Wroclaw Tech. U.]↗

Efficient algorithms for dilated mappings of binary trees

The problem is addressed to find a 1-1 mapping of the vertices of a binary tree onto those of a target binary tree such that the son of a node on the first binary tree is mapped onto a descendent of the image of that node in the second binary tree. There are two natural measures of the cost of this mapping, namely the dilation cost, i.e., the maximum distance in the target binary tree between the images of vertices that are adjacent in the original tree. The other measure, expansion cost, is defined as the number of extra nodes/edges to be added to the target binary tree in order to ensure a 1-1 mapping. An efficient algorithm to find a mapping of one binary tree onto another is described. It is shown that it is possible to minimize one cost of mapping at the expense of the other. This problem arises when designing pipelined arithmetic logic units (ALU) for special purpose computers. The pipeline is composed of ALU chips connected in the form of a binary tree. The operands to the pipeline can be supplied to the leaf nodes of the binary tree which then process and pass the results up to their parents. The final result is available at the root. As each new application may require a distinct nesting of operations, it is useful to be able to find a good mapping of a new binary tree over existing ALU tree. Another problem arises if every distinct required binary tree is known beforehand. Here it is useful to hardwire the pipeline in the form of a minimal supertree that contains all required binary trees.

Iqbal, M. Ashraf↗