Modern intrapartum fetal health assessments are currently limited to monitoring heart rate and spatial parameters, neglecting critical biomarkers that remain unmeasurable with today's clinical devices without performing surgery. Without precise evaluations of oxygen levels and blood acidity, clinicians are forced to rely on postnatal assessments to gauge fetal well-being, a delay that may obscure timely intervention. Fetal blood pH is a vital indicator of acid-base balance and cellular health, as any deviation could indicate potential health risks such as hypoxia and acidemia. In this study, we leverage the indirect relationship between pH and oxygen saturation to estimate fetal blood pH non-invasively using near-infrared (NIR) spectroscopy with wavelengths optimized for light transmission depth and oxygen saturation measurements. A convolutional neural network (CNN) extracts features from the acquired data, enabling accurate prediction of fetal blood pH using our machine learning (ML) model. Evaluation using hypoxic sheep models demonstrated an average prediction error of just 0.023 pH units, with all rounds maintaining errors below 0.05 pH units.

Evaluation of fetal health during pregnancy is highly dependent on monitoring of fetal heart rate (FHR). New technologies emerge, such as the transabdominal fetal pulse oximeter (TFO), a non-invasive, light-based measurement device, to provide obstetricians with additional fetal physiological markers such as fetal oxygen saturation. Estimation of FHR from TFO's acquired photoplethysmogram (PPG) signals is necessary for deriving oxygen saturation. Non-invasive optical sensing of deep fetal tissue is inherently challenged by low signal-to-noise ratio, and unpredictable anatomical and physiological dynamics, which render a particular sensor design suboptimal. Multiple sensors can conceptually enable the system to operate more robustly under such dynamics, assuming the data acquired by different sensors can be adaptively integrated to form a coherent view of the tissue. In this paper, we present an algorithm for data fusion at several levels of information abstraction, raw data, feature, and decision levels, to improve FHR estimation. We validate the proposed technique via in-vivo data collected in gold-standard pregnant ewe experiments using TFO. The root-mean-squared error of our three-level hierarchical data fusion compared to a single-level and two-level fusion improved by over 59% and 51%, respectively. This underscores the robustness of our approach in overcoming optical deep tissue sensing challenges.

Traditional approaches to intrapartum fetal monitoring, based on interpretation of fetal heart rate (FHR) tracings, have high false positive rates for detection of fetuses at risk of birth asphyxia. Transabdominal Fetal Pulse Oximetry (TFO) promises to supplement FHR trace interpretation through noninvasive sensing of fetal blood oxygen saturation$(\text{SPpO}_{2})$from photoplethysmography (PPG) signals acquired through the maternal abdomen. However, the acquired signals, referred to as mixed PPG, contain contributions from both maternal superficial tissue layers and fetal tissue, as well as other noise sources. We propose Phase-Synchronized Averaging for Fetal Signal Enhancement (PSAFE), a novel algorithm that leverages fetal heart phase information to align and average mixed PPG segments. Evaluation using in-vivo data collected from pregnant ewe models demonstrate that PSAFE yielded a 43.4% reduction in mean absolute error, and a 25.9% improvement in correlation for$\text{fSpO}_{2}$estimation, compared to a leading alternative approach.

We present a method, referred to as Deep Harmonic Finesse (DHF), for separation of non-stationary quasi-periodic signals when limited data is available. The problem frequently arises in wearable systems in which, a combination of quasi-periodic physiological phenomena give rise to the sensed signal, and excessive data collection is prohibitive. Our approach utilizes prior knowledge of time-frequency patterns in the signals to mask and in-paint spectrograms. This is achieved through an application-inspired deep harmonic neural network coupled with an integrated pattern alignment component. The network's structure embeds the implicit harmonic priors within the time-frequency domain, while the pattern-alignment method transforms the sensed signal, ensuring a strong alignment with the network. The effectiveness of the algorithm is demonstrated in the context of non-invasive fetal monitoring using both synthesized and in vivo data. When applied to the synthesized data, our method exhibits significant improvements in signal-to-distortion ratio (26% on average) and mean squared error (80% on average), compared to the best competing method. When applied to in vivo data captured in pregnant animal studies, our method improves the correlation error between estimated fetal blood oxygen saturation and the ground truth by 80.5% compared to the state of the art.

Quasi-periodic signal separation poses a significant challenge in wearable systems with limited data, particularly when the measured signal, influenced by multiple physiological sources, is under-represented. Addressing this issue, we introduce Deep Quasi-Periodic Priors (DQPP), a signal separation method for non-stationary, single-detector, quasi-periodic signals using an isolated input data. This approach incorporates masking and in-painting of the time-frequency spectrogram, while integrating prior harmonic and temporal patterns within the deep neural network structure. Moreover, a pattern alignment unit transforms the input signal's time-frequency patterns to closely align with the deep harmonic neural structure. The efficacy of DQPP is demonstrated in non-invasive fetal oxygen monitoring, using both synthetic and in vivo data, underscoring its applicability and potential in wearable technology.

Dicrotic Notch (DN), one of the most significant and indicative features of the arterial blood pressure (ABP) waveform, becomes less pronounced and thus harder to identify as a matter of aging and pathological vascular stiffness. Generalizable and automatic DN identification for such edge cases is even more challenging in the presence of unexpected ABP waveform deformations that happen due to internal and external noise sources or pathological conditions that cause hemodynamic instability. We propose a physics-aware approach, named Physiowise (PW), that first employs a cardiovascular model to augment the original ABP waveform and reduce unexpected deformations, then apply a set of predefined rules on the augmented signal to find DN locations. We have tested the proposed method on in-vivo data gathered from 14 pigs under hemorrhage and sepsis study. Our result indicates 52% overall mean error improvement with 16% higher detection accuracy within the lowest permitted error range of 30 ms. An additional hybrid methodology is also proposed to allow combining augmentation with any application-specific user-defined rule set.

In wearable optical sensing applications whose target tissue is not superficial, such as deep tissue oximetry, the task of embedded system design has to strike a balance between two competing factors. On one hand, the sensing task is assisted by increasing the radiated energy into the body, which in turn, improves the signal-to-noise ratio (SNR) of the deep tissue at the sensor. On the other hand, patient safety consideration imposes a constraint on the amount of radiated energy into the body. In this paper, we study the trade-offs between the two factors by exploring the design space of the light source activation pulse. Furthermore, we propose BASS, an algorithm that leverages the activation pulse design space exploration, which further optimizes deep tissue SNR via spectral averaging, while ensuring the radiated energy into the body meets a safe upper bound. The effectiveness of the proposed technique is demonstrated via analytical derivations, simulations, and in vivo measurements in both pregnant sheep models and human subjects.

State-of-the-art convolutional neural networks are designed to identify numerous object classes. Inference using such complex networks is fairly resource intensive, prohibiting their deployment on resource-constrained edge devices. In this context, we make two observations: First, the ability to classify an exhaustive list of categories is excessive for the demands of most IoT applications. Furthermore, designing a new custom-designed CNN for each new IoT application is inefficient. The observations motivate us to consider if one can utilize an existing optimized CNN model to automatically construct a competitive CNN for a given IoT application whose objects of interest are a fraction of categories that the original CNN was designed to classify, such that the model’s inference resource requirement is proportionally scaled down. We use the termresource scalabilityto refer to this concept, and develop a methodology for automated synthesis of resource scalable CNNs from an optimized baseline CNN. The synthesized CNN has sufficient learning capacity for handling the given IoT application requirements, and yields competitive accuracy. The proposed approach is fast, and unlike the presently common practice of neural network design, does not require iterative rounds of training trial and error to find an optimal architecture. Experimental results showcase the efficacy of the approach, and highlight its complementary nature with respect to existing model compression techniques, such as pruning and quantization.

Current intrapartum fetal well-being assessment is performed using electronic fetal monitoring (EFM), technically referred to as cardiotocography (CTG), which transabdominally monitors fetal heart rate (FHR) in relationship to maternal uterine contractions. Sometimes the deceleration in FHR following a uterine contraction can be sign of fetal hypoxic distress, but it may also be a normal physiological response. Multiple studies have shown that EFM has a high false positive rate for detecting fetal hypoxia. This has caused a rise in emergency Cesarean section (C-section) deliveries performed in the US over the years, while the rates of various conditions associated with anoxic brain injury at birth remain unchanged. The underlying problem is that many factors other than hypoxia can cause non-reassuring CTG traces and a more objective measure of oxygen supply to the fetal brain is not conveniently available. We are working to develop a transabdominal fetal pulse oximetry (TFO) system to non-invasively measure fetal arterial blood oxygen saturation (FSpO2) in order to enhance intrapartum fetal monitoring. This paper gives an overview of the past and ongoing work performed to develop TFO, highlights the main engineering and clinical challenges faced and presents preliminary results that demonstrate feasibility of TFO in both pregnant sheep models and human subjects.

Field-programmable gate array (FPGA)-based accelerators for convolutional neural network (CNN) inference have received significant attention in recent years. The reported designs tend to adopt a similar underlying approach based on multiplier-accumulator (MAC) arrays, which yields strong demand for the available on-chip DSP blocks, while leaving FPGA logic and memory resources underutilized. The practical outcome is that the computational roof of the accelerator is bound by the number of DSP blocks offered by the target FPGA. In addition, integrating the CNN accelerator with other functional units that may also need DSP blocks would degrade the inference performance. Leveraging the robustness of inference accuracy to limited arithmetic precision, we propose a transformation to the convolution computation, which leads to transformation of the accelerator design space and relaxes the pressure on the required DSP resources. Through analytical and empirical evaluations, we demonstrate that our approach enables us to strike a favorable balance between utilization of the FPGA on-chip memory, logic, and DSP resources, due to which, our accelerator considerably outperforms state of the art. We report the effectiveness of our approach on a variety of FPGA devices, including Cyclone-V, Stratix-V, and Arria-10, which are used in large number of applications, ranging from embedded settings to high performance computing. Our proposed technique yields 1.5x throughput improvement and 4x DSP resource reduction compared to the best frequency domain convolution-based accelerator, and 2.5x boost in raw arithmetic performance and 8.4x saving in DSPs compared to a state-of-the-art sparse convolution-based accelerator.

Hardware accelerators for convolutional neural network (CNN) inference have been extensively studied in recent years. The reported designs tend to utilize a similar underlying architecture based on multiplier-accumulator (MAC) arrays, which has the practical consequence of limiting the FPGA-based accelerator performance by the number of available on-chip DSP blocks, while leaving other resource under-utilized. To address this problem, we consider a transformation to the convolution computation, which leads to transformation of the accelerator design space and relaxes the pressure on the required DSP resources. We demonstrate that our approach enables us to strike a judicious balance between utilization of the on-chip memory, logic, and DSP resources, due to which, our accelerator considerably outperforms state of the art. We report the effectiveness of our approach on a Stratix-V GXA7 FPGA, which shows 55% throughput improvement, while using 6.25% less DSP blocks, compared to the best reported CNN accelerator on the same device.

Non-invasive transabdominal fetal oximetry (TFO) has the potential to improve delivery outcomes by providing physicians with an objective metric of fetal well-being during labor. Fundamentally, the technology is based on sending light through the maternal abdomen to investigate deep fetal tissue, followed by detection and processing of the light that returns (via scattering) to the outside of the maternal abdomen. The placement of the photodetector in relation to the light source critically impacts TFO system performance, including its operational robustness in the face of fetal depth variation. However, anatomical differences between pregnant women cause the fetal depths to vary drastically, which further complicates the optical probe (optode) design optimization. In this paper, we present a methodology to solve this problem. We frame optode design space exploration as a multi-objective optimization problem, where hardware complexity (cost) and performance across a wider patient population (robustness) form competing objectives. We propose a model-based approach to characterize the Pareto-optimal points in the optode design space, through which a specific design is selected. Experimental evaluation via simulation and in vivo measurement on pregnant sheep support the efficacy of our approach.

Many Internet-of-Things (IoT) applications demand fast and accurate understanding of a few key events in their surrounding environment. Deep Convolutional Neural Networks (CNNs) have emerged as an effective approach to understand speech, images, and similar high-dimensional data types. Algorithmic performance of modern CNNs, however, fundamentally relies on learning class-agnostic hierarchical features that only exist in comprehensive training datasets with many classes. As a result, fast inference using CNNs trained on such datasets is prohibitive for most resource-constrained IoT platforms. To bridge this gap, we present a principled and practical methodology for distilling a complex modern CNN that is trained to effectively recognize many different classes of input data into an application-dependent essential core that not only recognizes the few classes of interest to the application accurately but also runs efficiently on platforms with limited resources. Experimental results confirm that our approach strikes a favorable balance between classification accuracy (application constraint), inference efficiency (platform constraint), and productive development of new applications (business constraint).

Many patients who suffer from spinal cord injuries (SCI) also suffer from neurogenic bladder dysfunction, and lack the sensation and control of their bladder. In order to alleviate the build up of bladder pressure from urine production and promote good renal health, it is recommended to perform clean intermittent catheterization (CIC) every 2 to 4 hours throughout the day. However, since urine production is not constant, sometimes the bladder will fill with urine to capacity before the recommended CIC time causing the patient to leak, adding unnecessary embarrassment. As such, incontinence is the primary concern of many SCI patients. Sadly, there are no practical solutions available on the market that addresses this concern. In this work, we investigate using near-infrared spectroscopy to develop a wearable and non-invasive bladder volume sensing system to provide timely alerts to SCI patients based on their current bladder volume. We showcase the feasibility of such a system using an optical phantom that mimics the bladder and by performing ex vivo measurements on a pig bladder and intestines.

Convolutional neural networks (CNNs) have led to remarkable progress in a number of key pattern recognition tasks, such as visual scene understanding and speech recognition, that potentially enable numerous applications. Consequently, there is a significant need to deploy trained CNNs to resource-constrained embedded systems. Inference using pretrained modern deep CNNs, however, requires significant system resources, including computation, energy, and memory space. To enable efficient implementation of trained CNNs, a viable approach is to approximate the network with an implementation-friendly model with only negligible degradation in classification accuracy. We present Ristretto, a CNN approximation framework that enables empirical investigation of the tradeoff between various number representation and word width choices and the classification accuracy of the model. Specifically, Ristretto analyzes a given CNN with respect to numerical range required to represent weights, activations, and intermediate results of convolutional and fully connected layers, and subsequently, it simulates the impact of reduced word width or lower precision arithmetic operators on the model accuracy. Moreover, Ristretto can fine-tune a quantized network to further improve its classification accuracy under a given number representation and word width configuration. Given a maximum classification accuracy degradation tolerance of 1%, we use Ristretto to demonstrate that three ImageNet networks can be condensed to use 8-bit dynamic fixed point for network weights and activations. Ristretto is available as a popular open-source software project and has already been viewed over 1,000 times on Github as of the submission of this brief.

Many early stage lung cancer patients have resectable tumors, however, their cardiopulmonary function needs to be properly evaluated before they are deemed operative candidates. Such patients are typically asked to undergo standard pulmonary function tests, including cardiopulmonary exercise tests (CPET) or stair climbs. The standard tests are conducted only at selected healthcare provider locations, and are labor intensive. In addition, they are sometimes ineffective due to patient co-morbidities, such as limited mobility, which limits patient participation. To address these shortcomings, we envision that cardiopulmonary function can be evaluated in the patient's environment using an inexpensive wearable device during routine physical activities. We present a cloud-connected mask that is fitted with CO2, O2, flow volume, and accelerometer sensors. The data collected from the device is transmitted to a cloud service, which facilitates utilization of various data mining algorithms for extraction of insights from the data. As a necessary first step toward cardiopulmonary function evaluation, we study automatic recognition of the user's physical activity from mask sensors data via an empirical analysis of several data representation and classification algorithms. The results demonstrate accurate activity recognition using mask sensors, and underscore the potential of our approach for cardiopulmonary function evaluation.

Current technology used for monitoring fetal well-being has been ineffective at reducing rates of harm to the fetus during the intrapartum period, yet its adoption has significantly increased the number of emergency C-sections performed. Transabdominal fetal pulse oximetry (TFO) aims to reduce the number of surgical interventions through non-invasive measurements of fetal oxygen saturation. When developing an optode for TFO, it is important to select design parameters that will maximize the measurement of the fetal signal. In this paper, we optimize the source-detector distance and wavelengths through Monte Carlo simulations using a multi-layered tissue model for various fetal depths. The results were validated by developing an optical probe with two wavelengths of light to observe pulsating arterial tissue through an optical phantom that mimics the maternal abdomen as a step towards oximetry. Our results show that 735nm and 850nm seem to be the optimal selection of peak wavelengths of light sources to obtain a stronger fetal signal for the fetal depths between 2-5 cm. Improving the signal sensitivity is approached by increasing the spacing between the source and detector, and is limited by the noise-equivalent power of the detector.

Despite their remarkable performance in various machine intelligence tasks, the computational intensity of Convolutional Neural Networks (CNNs) has hindered their widespread utilization in resource-constrained embedded and IoT systems. To address this problem, we present a framework for synthesis of efficient CNN inference software targeting mobile SoC platforms. We argue that thread granularity can substantially impact the performance and energy dissipation of the synthesized inference software, and demonstrate that launching the maximum number of logical threads, often promoted as a guiding principle by GPGPU practitioners, does not result in an efficient implementation for mobile SoCs. We hypothesize that the runtime of a CNN layer on a particular SoC platform can be accurately estimated as a linear function of its computational complexity, which may seem counter-intuitive, as modern mobile SoCs utilize a plethora of heterogeneous architectural features and dynamic resource management policies. Consequently, we develop a principled approach and a data-driven analytical model to optimize granularity of threads during CNN software synthesis. Experimental results with several modern CNNs mapped to a commodity Android smartphone with a Snapdragon SoC show up to 2.37X speedup in application runtime, and up to 1.9X improvement in its energy dissipation compared to existing approaches.

Deep Convolutional Neural Networks (DCNNs) exhibit remarkable performance in a number of pattern recognition and classification tasks. Modern DCNNs involve many millions of parameters and billions of operations. Inference using such DCNNs, if implemented as software running on an embedded processor, results in considerable execution time and energy consumption, which is prohibitive in many mobile applications. Field-programmable gate array (FPGA)-based acceleration of DCNN inference is a promising approach to improve both energy consumption and classification throughput. However, the engineering effort required for development and verification of an optimized FPGA-based architecture is significant. In this article, we present PLACID, an automated PLatform for Accelerator CreatIon for DCNNs. PLACID uses an analytical approach to characterization and exploration of the implementation space. PLACID enables generation of an accelerator with the highest throughput for a given DCNN on a specific target FPGA platform. Subsequently, it generates an RTL level architecture in Verilog, which can be passed onto commercial tools for FPGA implementation. PLACID is fully automated, and reduces the accelerator design time from a few months down to a few hours. Experimental results show that architectures synthesized by PLACID yield 2× higher throughput density than the best competing approach.

Deep Convolutional Neural Networks (DCNN) have proven to be very effective in many pattern recognition applications, such as image classification and speech recognition. Due to their computational complexity, DCNNs demand implementations that utilize custom hardware accelerators to meet performance and energy-efficiency constraints. In this paper we propose an FPGA-based accelerator architecture which leverages all sources of parallelism in DCNNs. We develop analytical feasibility and performance estimation models that take into account various design and platform parameters. We also present a design space exploration algorithm for obtaining the implementation with the highest performance on a given platform. Simulation results with a real-life DCNN demonstrate that our accelerator outperforms other competing approaches, which disregard some sources of parallelism in the application. Most notably, our accelerator runs 1.9× faster than the state-of-the-art DCNN accelerator on the same FPGA device.

Many mobile applications running on smartphones and wearable devices would potentially benefit from the accuracy and scalability of deep CNN-based machine learning algorithms. However, performance and energy consumption limitations make the execution of such computationally intensive algorithms on mobile devices prohibitive. We present a GPU-accelerated library, dubbed CNNdroid [1], for execution of trained deep CNNs on Android-based mobile devices. Empirical evaluations show that CNNdroid achieves up to 60X speedup and 130X energy saving on current mobile devices. The CNNdroid open source library is available for download at https://github.com/ENCP/CNNdroid

Models of computation abstract away a number of implementation details in favor of well-defined semantics. While this has unquestionable benefits, we argue that analysis of models solely based on operational semantics (implementation-oblivious analysis) is unfit to drive implementation design space exploration. Specifically, we study the tradeoff between buffer size and streaming throughput in applications modeled as synchronous data flow (SDF) graphs. We demonstrate the inherent inaccuracy of implementation-oblivious approach, which only considers SDF operational semantic. We propose a rigorous transformation, which equips the state of the art buffer-throughput tradeoff analysis technique with implementation awareness. Extensive empirical evaluation show that our approach results in significantly more accurate estimates in streaming throughput at the model level, while running two orders of magnitude faster than cycle-accurate simulation of implementations.

Streaming network traffic measurement and analysis is critical for detecting and preventing any real-time anomalies in the network. The high speeds and complexity of today's networks, coupled with ever evolving threats, necessitate closing of the loop between measurements and their analysis in real time. The ensuing system demands high levels of programmability and processing where streaming measurements adapt to the changing network behavior in a goal-oriented manner. In this work, we exploit the features and requirements of the problem and develop an application-specific FPGA-based closed-loop measurement (CLM) system. We make novel use of fine-grained partial dynamic reconfiguration (PDR) as underlying reprogramming paradigm, performing low-latency just-in-time compiled logic changes in FPGA fabric corresponding to the dynamic measurement requirements. Our innovative dynamically reconfigurable socket offers 3× logic savings over conventional static solutions, while offering much reduced reconfiguration latencies over conventional PDR mechanisms. We integrate multiple sockets in a highly parallel CLM framework and demonstrate its effectiveness in identifying heavy flows in streaming network traffic. The results using an FPGA prototype offer 100 percent detection accuracy while sustaining increasing link speeds.

We study the problem of mapping concurrent tasks of an application to cores of a chip multiprocessor that utilize circuit-switched interconnect and global asynchronous local synchronous (GALS) clocking domains. We develop a configurable algorithm that naturally handles a number of practical requirements, such as architectural features of the target platform, core failures, and hardware accelerators, and in addition, is scalable to a large number of tasks and cores. Experiments with several real life applications show that our algorithm outperforms manual mapping, integer linear programming-based mapping after ten days of solver run time, and a recent packet-switched network on chip-based task mapper through which, we underscore the unique requirements of task mapping for circuit-switched GALS architectures.

Online network traffic measurements and analysis is critical for detecting and preventing any real-time anomalies in the network. We propose, implement, and evaluate an online, adaptive measurement platform, which utilizes real-time traffic analysis results to refine subsequent traffic measurements. Central to our solution is the concept of Multi-Resolution Tiling (MRT), a heuristic approach that performs sequential analysis of traffic data to zoom into traffic subregions of interest. However, MRT is sensitive to transient traffic spikes. In this paper, we propose three novel traffic streaming algorithms that overcome the limitations of MRT and can cater to varying degrees of computational and storage budgets, detection latency, and accuracy of query response. We evaluate our streaming algorithms on a highly parallel and programmable hardware as well as a traditional software-based platforms. The algorithms demonstrate significant accuracy improvement over MRT in detecting anomalies consisting of synthetic hard-to-track elephant flows and global icebergs. Our proposed algorithms maintain the worst-case complexities of the MRT while incurring only a moderate increase in average resource utilization.

We study the problem of mapping concurrent tasks of an application modeled as a data flow graph onto processors of a GALS-based manycore platform. We propose a mapping algorithm called BAMSE, which exploits the characteristics of streaming applications and the specifications of the target architecture to optimize the mapping solution. Different configuration parameters embedded into the algorithm enable one to strike a balance between scalability of the approach and the quality of generated solutions. Experiments with several real life applications show that our algorithm outperforms hand-optimized manual mappings up to 65% in terms of longest inter-processor communication link, and as high as 19% with respect to total length of the links, when the two criteria are used as primary and secondary optimization objectives, respectively. Additionally, our algorithm delivers superior mappings compared to ILP generated solutions after 10 days of solver runtime.

We study the trade-off between throughput and memory footprint of embedded software that is synthesized from acyclic static dataflow (task graph) specifications targeting distributed memory multiprocessors. We identify iteration overlapping as a knob in the synthesis process by which one can trade application throughput for its memory requirement. Given an initial processor assignment and non-overlapped task schedule, we formally present underlying properties of the problem, such as constraints on a valid iteration overlapping, maximum possible throughput, and minimum memory footprint. Moreover, we develop an effective algorithm for generation of a rich set of design points that provide a range of trade-off options. Experimental results on a number of applications and architectures validate the effectiveness of our approach.

Variants of dataflow specification models are widely used to synthesize streaming applications for distributed-memory parallel processors. We argue that current practice of specifying streaming applications using rigid dataflow models, implicitly prohibits a number of platform oriented optimizations and hence limits portability and scalability with respect to number of processors. We motivate Functionally-cOnsistent stRucturally-MalLEabe Streaming Specification, dubbed FORMLESS, which refers to raising the abstraction level beyond fixed-structure dataflow to address its portability and scalability limitations. To demonstrate the potential of the idea, we develop a design space exploration scheme to customize the application specification to better fit the target platform. Experiments with several common streaming case studies demonstrate improved portability and scalability over conventional dataflow specification models, and confirm the effectiveness of our approach.

Streaming applications, which are abundant in many disciplines such as multimedia, networking, and signal processing, require efficient processing of a seemingly infinite sequence of input data. In the context of streaming software synthesis from data flow graphs, we study the inherent trade-off between memory requirement and compilation runtime, under a given task firing schedule. We utilize postscheduling analysis granularity to control the amount of details in characterization of buffer's spatio-temporal footprints. Subsequently, we transform the buffer allocation problem to two-dimensional packing of polygons, where complexity of the packing problem (e.g., polygon shapes) is determined by the analysis granularity. We develop an evolutionary packing optimization algorithm which readily yields buffer allocations. Experimental results highlight the trade-off between complexity of the analysis and the total buffer size of generated implementations. In addition, they show dramatic improvements in total buffer size, if one is willing to pay the additional cost in optimization runtime.

Streaming network traffic measurements and analysis is critical for detecting and preventing any real-time anomalies in the network. The high speeds and complexity of today's network make the traditional slow open-loop measurement schemes infeasible. We propose an alternate closed-loop measurement paradigm and demonstrate its practical realization. To the heart of our solution are three streaming algorithms that provide a tight integration between the measurement platform and the measurements. The algorithms cater to varying degrees of computational budgets, detection latency, and accuracy. We empirically evaluate our streaming solutions on a highly parallel and programmable measurement platform. The algorithms demonstrate a marked 100% accuracy increase from a recently proposed MRT algorithm in detecting DoS attacks made up of synthetic hard-to-track elephant flows. Our proposed algorithms maintain the worst case complexities of the MRT, while empirically demonstrating a moderate increase in average resource utilization.

Programmable analysis of network traffic is critical for wide range of higher level traffic engineering and anomaly detection applications. Such applications demand stateful and programmable network traffic measurements (NTM) at high throughputs. We exploit the features and requirements of NTM, and develop an application-specific FPGA based Partial Dynamic Reconfiguration (PDR) scheme that is tailored to NTM problem. PDR has traditionally been done through swapping of statically compiled FPGA configuration data. Besides being latency intensive, static compilation cannot take into account exact requirements as they appear during real-time in many applications like NTM. In this paper, we make novel use of fine-grained PDR, performing minute logic changes in real-time and demonstrate its effectiveness in a prototype solution for programmable and real-time NTM. We specifically make use of flexibility available through the application and present a number of novel tools and algorithms that enabled developing the BURAQ system. Our results show 4x area and 1.3x latency improvements of BURAQ from a comparative statically compiled recent solution.

Many embedded applications demand processing of a seemingly endless stream of input data in real-time. Productive development of such applications is typically carried out by synthesizing software from high-level specifications, such as data-flow graphs. In this context, we study the problem of inter-actor buffer allocation, which is a critical step during compilation of streaming applications. We argue that fine-grain analysis of buffers' spatio-temporal characteristics, as opposed to conventional live range analysis, enables dramatic improvements in buffer sharing. Improved sharing translates to reduction of the compiled binary memory footprint, which is of prime concern in many embedded systems. We transform the buffer allocation problem to two-dimensional packing using complex polygons. We develop an evolutionary packing algorithm, which readily yields buffer allocations. Experimental results show an average of over 7X and 2X improvement in total buffer size, compared to baseline and conventional live range analysis schemes, respectively.

Heterogeneous soft multiprocessor systems are likely to find a larger share in the application-specific computing market due to increasing cost and defect rates in foreseeable manufacturing technologies. We study the problem of mapping streaming applications onto heterogeneous soft dual-processor systems, in which processors' limited memory resources and application throughput form the outstanding constraints and objective, respectively. A key step in the compilation process is task assignment, where tasks are assigned to the processors. We develop a provably-effective algorithm for task assignment. Our algorithm is versatile, in that its formal properties hold for, and hence it is applicable to, a variety of platforms. Measurement of generated code size, and throughput of emulated systems validate the effectiveness of our approach. We advance the state-of-the-art by considerably outperforming two recent competitors in terms of both versatility and application throughput.

Incremental design methods can substantially improve products' time-to-market through efficient handling of engineering change orders (ECO). In this paper, we present a methodology for incrementally solving component implementation selection problem (CISP) in face of local or non-local perturbations. CISP, which refers to judicious selection of components implementation under system timing constraint, is a generic problem that implicitly or explicitly appears in many stages of CAD flow. For a commonly-used formulation of CISP, we discuss necessary and sufficient conditions for optimality of the solution. Based on the optimality conditions, we develop an algorithm that maintains both validity and optimality of a solution under incremental changes. We evaluated our approach by incrementally updating the threshold voltage assignment solution for a netlist going through engineering changes. On average, our method ran 283 times faster than the full solver, while delivering the same results.

We present a methodology for pipelined software synthesis of streaming applications. First, we develop a versatile task assignment algorithm capable of optimizing realistically-arbitrary cost functions for two cores. The algorithm is exact (i.e., theoretically optimal) contrary to existing heuristics. Second, our approximation technique provides an adjustable knob to trade solution quality with algorithm runtime and memory. Third, we develop a recursive heuristic for more cores. FPGA-based emulated experiments validate our theoretical results. The exact algorithm yields 1.7 × throughput improvement. The approximation method offers a range of tradeoff points (e.g., 3 × faster with 20 × less memory) while degrading the throughput only 1% to 5%.

Dynamic reconfiguration imposes significant penalties in terms of performance and energy. Scheduling the execution of tasks on a dynamically reconfigurable device is therefore of critical importance. Likewise, other application domains have cost models that are effectively the same as dynamic reconfiguration; examples include: data transmission across multiprocessor systems; dynamic code updating and reprogramming of motes in sensor networks; and module allocation, wherein the sharing of resources effectively eliminates inherent reconfiguration costs. This article contributes a fully polynomial time approximation algorithm for the problem of scheduling independent tasks onto a fixed number of heterogeneous reconfigurable resources, where each task has a different hardware and software latency on each device; the reconfiguration latencies can also vary between resources. A general-purpose processor and a field programmable gate array were used to experimentally validate the proposed technique using a pair of encryption algorithms. The latencies of the schedules obtained by the approximation scheme were at most 1.1× longer than the optimal solution, which was found using integer linear programming; this result is better than the theoretical worst-case guarantee of the approximation algorithm, which was 1.999×. The length of the schedules obtained using list scheduling, a well-known polynomial time heuristic, were at most 2.6× longer than optimal.

Accurate and real-time traffic measurement is becoming increasingly critical for large variety of applications including accounting, bandwidth provisioning and security analysis. Existing network measurement techniques, however, have major difficulty dealing with large number of flows in today’s high-speed networks and offer limited scalability with increasing link speeds. Consequently, the current state of the art solutions have to resort to conservative sampling of the traffic stream and/or accounting for only a few frequent flows that often fail to provide accurate estimates of traffic features. In this paper, we present a novel hardware-software codesigned solution that is programmable and adaptable to runtime situations offering high-throughputs that can easily

Pipelined execution of streaming applications enable processing of high-throughput data under performance constraint. We present an integrated approach to synthesizing pipelined software for dual-core architectures. We target streaming applications modeled as task graphs that are amenable to static analysis. We develop a versatile task assignment algorithm that considers the combined effect of workload imbalance between processors and inter-processor communication. Our technique, which runs in pseudo-linear time, provably maximizes application throughput. Furthermore, we develop an approximation algorithm for task assignment whose complexity is strictly polynomial. It provides the designer with an adjustable knob to controllably trade solution quality with algorithm runtime and memory requirement. Empirical throughput measurements using an FPGA-based dual-core system validate our theoretical results. Our exact algorithm consistently outperforms a recent competitor. Compared to exact task assignment, the approximate method runs about 3 times faster, requires about 20 times less memory, and results in only 1% to 5% throughput loss.

We present a compilation technique that targets realtime applications running on embedded processors with combined dynamic voltage scaling (DVS) and adaptive body biasing (ABB) capabilities. Considering the delay and energy penalty of switching between operating modes of the processor, our compiler judiciously inserts mode switch instructions in selected locations of the code and generates executable binary that is guaranteed to meet the deadline constraint. More importantly, our algorithm runs very fast and comes reasonably close to the theoretical limit of energy optimization using DVS+ABB. At 65 nm technology, we improve the energy dissipation of the generated code by an average of11.4% under deadline constraints. While our technique's improvement in energy dissipation over conventional DVS is marginal (3%) at 130nm, the average improvement continues to grow to 4.7%, 8.8% and 15.4% for 90nm, 65nm and 45nm technology nodes, respectively. Compared to a recent ILP-based competitor, we improve the runtime by more than three orders of magnitude, while producing improved results

The component implementation selection problem (CISP) is to select the appropriate implementation for components of a design, such that the timing constraint is met and some global design objective is optimized. CISP is a generic problem that implicitly or explicitly appears in many stages of CAD flow. In this paper, we present a methodology for quick and cfficicnt updating of CISP solutions in facc of incremental engineering changes. For a commonly-used formulation, we discuss necessary and sufficient conditions for optimality of a CISP solution based on which, we develop an algorithm that maintains both validity and optimality of a solution subject to incremental changes. We implemented our approach to incrementally lipdate the threshold voltage assignment solution for a netlist going through engineering changes. On average, our method ran over 300 times faster than the “from-scratch” solver, while delivering the same results.

We present a methodology for synthesizing streaming applications, modeled as task graphs, for pipelined execution on multi-core architectures. We develop a task graph extraction and characterization framework that accurately determines the structure, computation and communication characteristics of application task graph from its specification in C. Furthermore, we develop a provably optimal algorithm that jointly balances the workload assigned to each core, and minimizes inter-core communication traffic. Experiment results show that our versatile method improves the through-put of streaming applications significantly under a variety of hardware configurations.

With continuing shrinkage of technology feature sizes, the share of leakage in total energy consumption of digital systems continues to grow. Coordinated supply voltage and body bias throttling enables the compiler to better optimize the total energy consumption of the system in future technology nodes. We present a compilation technique that targets realtime applications running on embedded processors with combined dynamic voltage scaling (DVS) and adaptive body biasing (ABB) capabilities. Considering the delay and energy penalty of switching between operating modes of the processor, our compiler judiciously inserts mode-switch instructions in selected locations of the code and generates executable binary that is guaranteed to meet the deadline constraint. More importantly, our algorithm runs very fast and comes reasonably close to the theoretical limit of energy optimization using DVS+ABB. At 65nm technology, we improve the energy dissipation of the generated code by an average of 33.20% under deadline constraints. While our technique's improvement in energy dissipation over conventional DVS is marginal (6.91%) at 130nm, the average improvement continues to grow to 13.19%, 22.97%, and 33.21% for 90nm, 65nm, and 45nm technology nodes, respectively. Compared to a recent ILP-based competitor, we improve the runtime by more than three orders of magnitude, while producing improved results.

With scaling of technology feature sizes, the share of leakage in total power consumption of digital systems continues to grow. Conventional dynamic voltage scaling (DVS) techniques fail to accurately address theimpact of scaling on system power consumption and hence, are incapable ofachieving energy efficient solutions. To overcome this problem, we utilizeadaptive body biasing (ABB) to adjust transistors' threshold voltage at runtime. We develop a leakage-aware compilation methodology that targets embedded processors with both DVS and ABBcapabilities. Our technique has the unique advantage of jointly optimizing active and leakage energy dissipation. Considering the delay and energy penalty of switching between operating modes of the processor and under deadline constraint, our compiler improves the energy consumption of the generated code by average of 13.07% and up to 30.26% at 90nm. While our technique's improvement in energy dissipation over conventional DVS is marginal (4.54%) at 130nm,the average improvement continues to grow to 7.8%, 15.94% and 29.56% for 90nm, 65nm and 45 technology nodes, respectively.

Traditionally, active power has been the primary source of power dissipation in CMOS designs. Although, leakage power is becoming increasingly more important as technology feature sizes continue to shrink, traditioinal power optimization techniques often neglect its contribution to total system power. In this paper, we present a power-aware compilation methodology that targets an embedded processor with both dynamic voltage scaling (DVS) and adaptive body biasing (ABB) capabilities. Our technique has the unique advantage of optimizing design power by jointly optimizing dynamic and leakage power dissipation. Considering the delay and energy penalty of swithching between processor modes, our compiler generates code with minimum power consumption under deadline constraints. Compared to not performing any optimization, or using DVS alone, our technique improves the power consumption of a number of embedded application kernels by 2 6 %, and 1 4 %, respectively.

In this paper, the authors propose a new design for feature detection used for tracking, which eliminates the need of a central computer to complete computations for the feature selection algorithm. Such a system constrains performance due to the delay in which data is transferred from camera to computer for processing. Our design suggests that feature detection computation can be done on a processor within the camera helping to reduce overall computation time for detection and increase performance for overall tracking system. However, these systems are often constrained by the processing power available to the camera. But with Benedetti and Perona's approach to Tomasi and Kanade's detection algorithm, such a design is possible to implement onto a camera system which would eliminate the delay and also improve performance over a tracking system designed on software

The routing channels of today's FPGAs consist of wire segments of various types, which allow the use of new techniques to enhance the routability of net segments in channels. In this paper we present an optimal greedy algorithm to switch the tracks that net segments are assigned to. This allows us to enhance the rerouting ability by capturing the features of the routing architecture. Suppose the number of tracks in the channels is given. The goal of this algorithm is to increase the number of routed segments of late rerouting requests. This is a good feature for supporting engineering change order (ECO) type of routing. Supporting ECO routing enables the routing algorithms to deal with later changes in routing requests. We used the routing architecture of VirtexII FPGAs from Xilinx as our target architecture and integrated our algorithm into the VPR FPGA routing tool. The experimental results show that our algorithm makes VPR router capable of handling 28.4% more rerouting for segments that are added to the design later

This paper presents a theoretical framework that solves optimally and in polynomial time many open problems in time budgeting. The approach unifies a large class of existing time-management paradigms. Examples include time budgeting for maximizing total weighted delay relaxation, minimizing the maximum relaxation, and min-skew time budget distribution. The authors develop a combinatorial framework through which we prove that many of the time-management problems can be transformed into a min-cost flow problem instance. The methodology is applied to intellectual-property-based datapath synthesis targeting field-programmable gate arrays. The synthesis flow maps the input operations to parameterized library modules during which different time budgeting policies have been applied. The techniques always improve the area requirement of the implemented test benches and consistently outperform a widely used competitor. The experiments verify that combining fairness and maximization objectives improves the results further as compared with pure maximum budgeting. The combined fairness and maximization objective improves the area by 25.8% and 28.7% in slice and LUT counts, respectively.

Tiny embedded systems have not been an ideal outfit for high performance computing due to their constrained resources-limitations in processing power, battery life, communication bandwidth, and memory constrain the applicability of existing complex medical analysis algorithms such as the electrocardiogram (ECG) analysis. Among various limitations, battery lifetime has been a major key technological constraint. In this paper, we address the issue of partitioning such a complex algorithm while the energy consumption due to wireless transmission is minimized. ECG analysis algorithms normally consist of preprocessing, pattern recognition, and classification. Considering the orientation of the ECG leads, we devise a technique to perform preprocessing and pattern recognition locally in small embedded systems attached to the leads. The features detected in the pattern recognition phase are considered for the classification. Ideally, if the features detected for each heartbeat reside in a single processing node, the transmission will be unnecessary. Otherwise, to perform classification, the features must be gathered on a local node and, thus, the communication is inevitable. We perform such a feature grouping by modeling the problem as a hypergraph and applying partitioning schemes which yield a significant power saving in wireless communications. Furthermore, we utilize dynamic reconfiguration by software module migration. This technique, with respect to partitioning, enhances the overall power saving in such systems. Moreover, it adaptively alters the system configuration in various environments and on different patients. We evaluate the effectiveness of our proposed techniques on MIT/BIH benchmarks and, on average, achieve 70 percent energy saving

Unlike their hard real-time counterparts, soft real-time applications are only expected to guarantee their "expected delay" over input data space. This paradigm shift calls for customized statistical design techniques to replace the conventional pessimistic worst case analysis methodologies. We present a novel statistical time-budgeting algorithm to translate the application expected delay constraint into its components' local delay constraints. We utilize the mathematical properties of the problem to quickly calculate the system expected delay and incrementally estimate the component utility variation with its timing relaxation. Our algorithm determines the optimal maximum weighted timing relaxation of an application under expected delay constraint. Experimental results on core-based synthesis of several multimedia applications targeting field-programmable gate arrays show that our technique always improves the design area. Furthermore, it consistently outperforms optimal time budgeting under hard real-time constraint, which is the best existing competitor. Design area improvements were up to 26% and averaged about 17% on several MediaBench applications.

The routing channels of today's FPGAs consist of wire segments of various types. This routing architecture makes us capable of exploiting some new techniques to enhance the routability of net segments in channels in order to support engineering change order (ECO). In this paper we present an optimal greedy algorithm to switch the track, which each net segment is assigned to, in order to enhance the routability of newly added nets for enabling ECO. We used the routing architecture of Virtex II FPGAs from Xilinx as our target routing architecture and integrated our algorithm into VPR FPGA routing tool. The experimental result show that the algorithm reduces the number of Tracks by 9% in average. It allows 28.4% more rerouting than the existing router of VPR tool, which is based on Dijkestra's maze router algorithm.

We present time budgeting as an efficient technique for implementation selection. We discuss discreteness in library and present an optimal algorithm for a special case of the problem. The algorithm is extended to construct a heuristic for the general case, and is experimented on the gate-level threshold voltage assignment problem in dual V/sub t/ technology. Experimental results show that our approach reduces the leakage current by close to an order of magnitude, with no or negligible delay penalty. Compared to existing algorithms, our technique outperforms a recent LP-based competitor by 33%.

This work presents a theoretical framework that optimally solves many open problems in time budgeting. Our approach unifies a large class of existing time-management paradigms. Examples include time budgeting for maximizing total weighted delay relaxation, minimizing the maximum relaxation and min-skew time budget distribution. We show that many of the time management problems can be transformed into a min-cost flow instance that can be optimally and efficiently solved through well-known combinatorial techniques. Experiments include mapping of several designs, which are implemented using parameterized CoreGen IP cores, on Xilinx FPGA devices. Different time budgeting policies have been applied during the mapping stage. Our time management techniques always improved the area requirement of the implemented testbenches compared to a widely-used path-based method. We also compared the maximum budgeting and fairness in delay budget assignments. Our experimental results show that an average improvement of 19% in area can be achieved when fairness and maximum budgeting policies are combined, compared to pure maximum budgeting.

The recent past has seen a tremendous increase in the size of design circuits that can be implemented in a single FPGA. The size and complexity of modern FPGAs has far outpaced the innovations in FPGA physical design. The problems faced by FPGA designers are similar in nature to those that preoccupy ASIC designers, namely, interconnect delays and design management. However, this paper will show that a simple re-targeting of ASIC physical design methodologies and algorithms to the FPGA domain will not suffice. We will show that several well researched problems in the ASIC world need new problem formulations and algorithms research to be useful for today's FPGAs. Partitioning, floorplanning, placement, delay estimation schemes are only some of the topics that need complete overhaul. We will give problem formulations, motivated by experimental results, for some of these topics as applicable in the FPGA domain.

Excess delay that each component of a design can tolerate under a given timing constraint is referred to as delay budget. Delay budgeting has been widely exploited to improve the design quality in very large scale integrated computer-aided design flow. The objective of the delay-budgeting problem investigated in this paper is to maximize the total delay budget assigned to each node in a directed acyclic graph under a given timing constraint. Due to the discreteness of the timing of the components in the libraries during design-optimization flow, discrete solution for delay budgeting is essential. We present an optimal integer delay-budgeting algorithm. We prove that the problem can be solved optimally in polynomial time. In addition, we look at different extensions of the delay-budgeting problem, such as maximization of weighted summation of delay budgets assigned to the nodes with constraints on the lower and upper bounds on the delay budget allocated to each node. We prove that for both aforementioned extensions, our algorithm can produce an optimal integer solution in polynomial time. Our algorithm is generic and can be applied at different design tasks at different levels of abstraction. We applied our proposed optimal delay-budgeting algorithm in library mapping during datapath synthesis on a field programmable gate array (FPGA) platform, using preoptimized cores of FPGA libraries. For each application, we go through synthesis and place and route stages in order to obtain accurate results. Our optimal algorithm outperforms the zero-slack algorithm (Nair et al. 1989) in terms of area by 10% on average for all applications. In some applications, optimal delay budgeting can speedup runtime of place and route up to two times.

Reconfiguration delay is one of the major barriers in the way of dynamically adapting a system to its application requirements. The run-time reconfiguration delay is quite comparable to the application latency for many classes of applications and might even dominate the application run-time. In this paper, we present an efficient optimal algorithm for minimizing the run-time reconfiguration (context switching) delay of executing an application on a dynamically adaptable system. The system is composed of a number of cameras with embedded reconfigurable resources collaborating in order to track an object. The operations required to execute in order to track the object are revealed to the system at run-time and can change according to a number of parameters, such as the target shape and proximity. Similarly, we can assume that the applications comprising tasks are already scheduled and each of them has to be realized on the reconfigurable fabric in order to be executed.The modeling and the algorithm are both applicable to partially reconfigurable platforms as well as multi-FPGA systems. The algorithm can be directly applied to minimize the application run-time for the typical classes of applications, where the actual execution delay of the basic operations is negligible compared to the reconfiguration delay. We prove the optimality and the efficiency of our algorithm. We report the experimental results, which demonstrate a 2.5--40% improvement on the total run-time reconfiguration delay as compared to other heuristics.

In this paper, we present an efficient optimal algorithm for minimizing runtime reconfiguration (context switching) delay of executing an application on a reconfigurable system. We assume that the basic operations of the application are already scheduled and each of them has to be realized on the reconfigurable fabric in order to be executed. The modeling and algorithm are both applicable to partially reconfigurable platforms as well as Multi-FPGA systems. The algorithm can be directly applied to minimize the application runtime for many typical classes of applications, where the actual execution delay of basic operations is negligible compared to reconfiguration delay. We prove the optimality and efficiency of our algorithm and report experimental results, which demonstrate 40% to 2.5% improvement in total runtime reconfiguration delay.

Delay budget is an excess delay each component of a design can tolerate under a given timing constraint. Delay budgeting has been widely exploited to improve the design quality. We present an optimal integer delay budgeting algorithm. Due to numerical instability and discreteness of libraries of components during library mapping in design optimization flow, integer solution for delay budgeting is essential. We prove that integer budgeting problem - a 20-year old open problem in design optimization [7]- can be solved optimally in polynomial time. We applied optimal delay budgeting in mapping applications on FPGA platform using pre-optimized cores of FPGA libraries. For each application we go through synthesis and place and route stages in order to obtain accurate results. Our optimal algorithm outperforms ZSA algorithm [3] in terms of area by 10% on average for all applications. In some applications, optimal delay budgeting can speedup runtime of place_and_route up to 2 times.

The idea of managing the comprising computations of an application executed in an FPGA-based system is presented. An efficient algorithm for exploiting the timing slack of building blocks of the application is proposed. The slack of these blocks can be utilized by replacing them with slower but "cheaper" modules and by assigning the computations to the proper resources. Thus, our approach manages the comprising computations and system resources at the same time. This is performed without compromising the timing constraints of the application and can lead to significant improvements in power dissipation, computation accuracy or other design metrics based on the application domain. Our algorithm is well-suited for arbitrary tree computations. Moreover, it delivers solutions that are desirably close to the optimal solution. Experimental results for a number of object tracking applications executed on resources embedded in cameras, show a significant amount of slack utilization.

This paper presents a novel method to reduce routing congestion during placement stage. The proposed approach is used as a post-processing step in placement. Congestion reduction is based on local improvement on the existing layout. However, the approach has a global view of the congestion over the entire design. It uses integer linear programming (ILP) to formulate the problem of conflicts between multiple congested regions, and performs local improvement according to the solution of the ILP problem. The approximation algorithm of the formulated ILP problem is studied and good approximation bounds are given and proved. Experiments show that the proposed approach can effectively alleviate the congestion of global routing results. The low computational complexity of the proposed approach indicates its scalability on large designs.