Developing the capability to continuously and noninvasively monitor the mental health status of individuals is a critical focus in the mHealth domain. The use of passively-generated data gathered via smart and portable electronic devices to monitor specific indicators of mental health has shown potential to serve as an effective alternative to traditional intrusive survey-based approaches to monitoring mental health remotely. In this study, we propose a remote health monitoring framework for dynamic, flexible, and scalable assessment and detection of physiological precursors of a stress response. Our method comprises a smartwatch-based system for continuous monitoring of primary physiological signals, followed by a deep neural network architecture that performs the fusion and processing of the multi-modal sensor readings. We empirically validate our system on a cohort of university-affiliated members of the military. Our findings demonstrate the effectiveness of our passive-sensing system for tracking perceived stress, the results of which can be used to obtain a better understanding of patient behavior and improve personalized treatments1.

In many machine learning applications, we are faced with incomplete datasets. In the literature, missing data imputation techniques have been mostly concerned with filling missing values. However, the existence of missing values is synonymous with uncertainties not only over the distribution of missing values but also over target class assignments that require careful consideration. In this paper, we propose a simple and effective method for imputing missing features and estimating the distribution of target assignments given incomplete data. In order to make imputations, we train a simple and effective generator network to generate imputations that a discriminator network is tasked to distinguish. Following this, a predictor network is trained using the imputed samples from the generator network to capture the classification uncertainties and make predictions accordingly. The proposed method is evaluated on CIFAR-10 and MNIST image datasets as well as five real-world tabular classification datasets, under different missingness rates and structures. Our experimental results show the effectiveness of the proposed method in generating imputations as well as providing estimates for the class uncertainties in a classification task when faced with missing values.

As COVID-19 hounds the world, the common cause of finding a swift solution to manage the pandemic has brought together researchers, institutions, governments, and society at large. The Internet of Things (IoT), artificial intelligence (AI)-including machine learning (ML) and Big Data analytics-as well as Robotics and Blockchain, are the four decisive areas of technological innovation that have been ingenuity harnessed to fight this pandemic and future ones. While these highly interrelated smart and connected health technologies cannot resolve the pandemic overnight and may not be the only answer to the crisis, they can provide greater insight into the disease and support frontline efforts to prevent and control the pandemic. This article provides a blend of discussions on the contribution of these digital technologies, propose several complementary and multidisciplinary techniques to combat COVID-19, offer opportunities for more holistic studies, and accelerate knowledge acquisition and scientific discoveries in pandemic research. First, four areas, where IoT can contribute are discussed, namely: 1) tracking and tracing; 2) remote patient monitoring (RPM) by wearable IoT (WIoT); 3) personal digital twins (PDTs); and 4) real-life use case: ICT/IoT solution in South Korea. Second, the role and novel applications of AI are explained, namely: 1) diagnosis and prognosis; 2) risk prediction; 3) vaccine and drug development; 4) research data set; 5) early warnings and alerts; 6) social control and fake news detection; and 7) communication and chatbot. Third, the main uses of robotics and drone technology are analyzed, including: 1) crowd surveillance; 2) public announcements; 3) screening and diagnosis; and 4) essential supply delivery. Finally, we discuss how distributed ledger technologies (DLTs), of which blockchain is a common example, can be combined with other technologies for tackling COVID-19.

Healthcare big data remains under-utilized due to various incompatibility issues between the domains of data analytics and healthcare. The lack of generalizable iterative feature acquisition methods under budget and machine learning models that allow reasoning with a model’s uncertainty are two examples. Meanwhile, a boost to the available data is currently under way with the rapid growth in the Internet of Things applications and personalized healthcare. For the healthcare domain to be able to adopt models that take advantage of this big data, machine learning models should be coupled with more informative, germane feature acquisition methods, consequently adding robustness to the model’s results. We introduce an approach to feature selection that is based on Bayesian learning, allowing us to report the level of uncertainty in the model, combined with false-positive and false-negative rates. In addition, measuring target-specific uncertainty lifts the restriction on feature selection being target agnostic, allowing for feature acquisition based on a target of focus. We show that acquiring features for a specific target is at least as good as deep learning feature selection methods and common linear feature selection approaches for small non-sparse datasets, and surpasses these when faced with real-world data that is larger in scale and sparseness.

Effective representation learning of electronic health records is a challenging task and is becoming more important as the availability of such data is becoming pervasive. The data contained in these records are irregular and contain multiple modalities such as notes, and medical codes. They are preempted by medical conditions the patient may have, and are typically recorded by medical staff. Accompanying codes are notes containing valuable information about patients beyond the structured information contained in electronic health records. We use transformer networks and the recently proposed BERT language model to embed these data streams into a unified vector representation. The presented approach effectively encodes a patient's visit data into a single a distributed representation, which can be used for downstream tasks. Our model demonstrates superior performance and generalization on mortality, readmission and length of stay tasks using the publicly available MIMIC-III ICU dataset.

Completing a set of therapeutic exercises correctly and regularly is essential for early and safe recovery from knee reconstructive surgery. We propose EXTRA, a platform for monitoring and improving the quality of therapeutic exercises that the patients need to perform during the recovery. The data acquisition framework obtains observations of the knee movement using an embedded flex sensor in a hinged knee brace. A connected Android application transmits the data to the database real-time. We evaluated the accuracy of the knee joint angle measurement and the usability in a study with young healthy adults. The mean absolute error of the knee angle measurements was 13.31 degrees. The high score of the usability questionnaire indicates that EXTRA provides a user-friendly interface to motivate therapeutic exercises. EXTRA maintains high standards in accurately monitoring and interpreting the exercises. Our proposed platform has the potential to provide effective guidelines and improve the rehabilitation process for orthopedic professionals and patients.

In real-world scenarios, different features have different acquisition costs at test time which necessitates cost-aware methods to optimize the cost and performance tradeoff. This paper introduces a novel and scalable approach for cost-aware feature acquisition at test time. The method incrementally asks for features based on the available context that are known feature values. The proposed method is based on sensitivity analysis in neural networks and density estimation using denoising autoencoders with binary representation layers. In the proposed architecture, a denoising autoencoder is used to handle unknown features (i.e., features that are yet to be acquired), and the sensitivity of predictions with respect to each unknown feature is used as a context-dependent measure of informativeness. We evaluated the proposed method on eight different real-world data sets as well as one synthesized data set and compared its performance with several other approaches in the literature. According to the results, the suggested method is capable of efficiently acquiring features at test time in a cost- and context-aware fashion.

With the recent availability of Electronic Health Records (EHR) and great opportunities they offer for advancing medical informatics, there has been growing interest in mining EHR for improving quality of care. Disease diagnosis due to its sensitive nature, huge costs of error, and complexity has become an increasingly important focus of research in past years. Existing studies model EHR by capturing co-occurrence of clinical events to learn their latent embeddings. However, relations among clinical events carry various semantics and contribute differently to disease diagnosis which gives precedence to a more advanced modeling of heterogeneous data types and relations in EHR data than existing solutions. To address these issues, we represent how high-dimensional EHR data and its rich relationships can be suitably translated into HeteroMed, a heterogeneous information network for robust medical diagnosis. Our modeling approach allows for straightforward handling of missing values and heterogeneity of data. HeteroMed exploits metapaths to capture higher level and semantically important relations contributing to disease diagnosis. Furthermore, it employs a joint embedding framework to tailor clinical event representations to the disease diagnosis goal. To the best of our knowledge, this is the first study to use Heterogeneous Information Network for modeling clinical data and disease diagnosis. Experimental results of our study show superior performance of HeteroMed compared to prior methods in prediction of exact diagnosis codes and general disease cohorts. Moreover, HeteroMed outperforms baseline models in capturing similarities of clinical events which are examined qualitatively through case studies.

Remote health monitoring (RHM) systems are becoming more widely adopted by clinicians and hospitals to remotely monitor and communicate with patients while optimizing clinician time, decreasing hospital costs, and improving quality of care. In the Women's heart health study (WHHS), we developed Wanda-cardiovascular disease (CVD), where participants received healthy lifestyle education followed by six months of technology support and reinforcement. Wanda-CVD is a smartphone-based RHM system designed to assist participants in reducing identified CVD risk factors through wireless coaching using feedback and prompts as social support. Many participants benefitted from this RHM system. In response to the variance in participants' success, we developed a framework to identify classification schemes that predicted successful and unsuccessful participants. We analyzed both contextual baseline features and data from the first month of intervention such as activity, blood pressure, and questionnaire responses transmitted through the smartphone. A prediction tool can aid clinicians and scientists in identifying participants who may optimally benefit from the RHM system. Targeting therapies could potentially save healthcare costs, clinician, and participant time and resources. Our classification scheme yields RHM outcome success predictions with an F-measure of 91.9%, and identifies behaviors during the first month of intervention that help determine outcome success. We also show an improvement in prediction by using intervention-based smartphone data. Results from the WHHS study demonstrates that factors such as the variation in first month intervention response to the consumption of nuts, beans, and seeds in the diet help predict patient RHM protocol outcome success in a group of young Black women ages 25-45.

Detecting short-duration events from continuous sensor signals is a significant challenge in the domain of wearable devices and health monitoring systems. Time-series segmentation refers to the challenge of subdividing a continuous stream of data into discrete windows, which can be individually processed using statistical classifiers or other algorithms. In this paper, we propose an algorithm for segmenting time-series signals and detecting short-duration data in the domain of lightweight embedded systems with real-time constraints. First, we demonstrate an approach for signal segmentation using a simple binary classifier. Next, we show how a novel two-stage classification algorithm can reduce computational overhead compared to a single-stage approach. Our proposed scheme is benchmarked using an audio-based nutrition-monitoring case study.

Asthma is the most prevalent chronic disease among pediatrics, as it is the leading cause of student absenteeism and hospitalization for those under the age of 15. To address the significant need to manage this disease in children, the authors present a mobile health (mHealth) system that determines the risk of an asthma attack through physiological and environmental wireless sensors and representational state transfer application program interfaces (RESTful APIs). The data is sent from wireless sensors to a smartwatch application (app) via a Health Insurance Portability and Accountability Act (HIPAA) compliant cryptography framework, which then sends data to a cloud for real-time analytics. The asthma risk is then sent to the smartwatch and provided to the user via simple graphics for easy interpretation by children. After testing the safety and feasibility of the system in an adult with moderate asthma prior to testing in children, it was found that the analytics model is able to determine the overall asthma risk (high, medium, or low risk) with an accuracy of 80.10±14.13%. Furthermore, the features most important for assessing the risk of an asthma attack were multifaceted, highlighting the importance of continuously monitoring different wireless sensors and RESTful APIs. Future testing this asthma attack risk prediction system in pediatric asthma individuals may lead to an effective self-management asthma program.

Among the major challenges in the realization of practical health monitoring systems is the identification of short-duration events from larger signals. Time-series segmentation refers to the challenge of subdividing a continuous stream of data into discrete windows, which are individually processed using statistical classifiers to recognize various activities or events. In this paper, we propose a probabilistic algorithm for segmenting time-series signals, in which window boundaries are dynamically adjusted when the probability of correct classification is low. Our proposed scheme is benchmarked using an audio-based nutrition-monitoring case-study. Our evaluation shows that algorithm improves the number of correctly classified instances from a baseline of 75% to 94% using the RandomForest classifier.

The advent of smart infrastructure or Internet of Things (IoT) has enabled scenarios in which objects with unique identifiers can communicate and transfer data over a network without human to human/computer interactions. Incorporating hardware in such networks is so cheap that it has opened the possibility of connecting just about anything from simple nodes to complex, remotely-monitored sensor networks. In the paper, we describe a low-cost scalable and potentially ubiquitous system for indoor remote health monitoring using low energy bluetooth beacons and a smartwatch. Our system was implemented in a rehabilitation facility in Los Angeles and the overall assessments revealed promising results.

A gait velocity estimation algorithm using the inertial sensors of a smartwatch is proposed. The peaks of accelerometer and gyroscope norms are detected at first. Then a Kalman Filter is employed to recover the peaks that are missed because of the arm swing. The Kalman filter combines the accelerometer and gyroscope norm peaks and robustly detect walking step events even in cases where there is a large arm swing. Walking velocity is then estimated using the step duration. It will be shown in this work that the gait velocity has a good correlation with the inverse of the square of the step duration. The model parameters are calculated by collecting the training data from 25 subjects: each subject walked 50 m six times with different walking speed and different arm swing speed. The standard deviation of walking velocity estimation error is 0.1009 m/s (without person dependent calibration) and 0.0630 m/s (with person dependent calibration). The average precision of 91.7% was achieved for the gait speed testing on the smartwatch platform over all the speed scenarios.

This paper presents a methodology for developing highly-accurate, continuous Arterial Blood Pressure (ABP) models using only Photoplethysmography (PPG). In contrast to prior approaches, we develop a system that exhibits dynamic temporal behavior which leads to increased accuracy in modeling ABP. We validate our approach using data from patients in the intensive care unit (ICU). We show that it is possible to build highly accurate, continuous blood pressure models using only finger pulse oximeters. Our methodology achieves accurate systolic blood pressure estimation with a root mean square error 2.58 ± 1.23 across the patient sample used. Furthermore, the continuous ABP signal is estimated with a root mean square error of 6.042 ± 3.26 and correlation coefficient of 0.95 ± 0.045. Our method enables designing robust Remote Health Monitoring Systems (RMS) for Heart Failure patients without requiring traditional blood pressure monitors.

Predicting the functional outcomes of spinal cord disorder patients after medical treatments, such as a surgical operation, has always been of great interest. Accurate posttreatment prediction is especially beneficial for clinicians, patients, care givers, and therapists. This paper introduces a prediction method for postoperative functional outcomes by a novel use of Gaussian process regression. The proposed method specifically considers the restricted value range of the target variables by modeling the Gaussian process based on a truncated Normal distribution, which significantly improves the prediction results. The prediction has been made in assistance with target tracking examinations using a highly portable and inexpensive handgrip device, which greatly contributes to the prediction performance. The proposed method has been validated through a dataset collected from a clinical cohort pilot involving 15 patients with cervical spinal cord disorder. The results show that the proposed method can accurately predict postoperative functional outcomes, Oswestry disability index and target tracking scores, based on the patient's preoperative information with a mean absolute error of 0.079 and 0.014 (out of 1.0), respectively.

Poor adherence to prescription medication can compromise treatment effectiveness and cost the billions of dollars in unnecessary health care expenses. Though various interventions have been proposed for estimating adherence rates, few have been shown to be effective. Digital systems are capable of estimating adherence without extensive user involvement and can potentially provide higher accuracy with lower user burden than manual methods. In this paper, we propose a smartwatch-based system for detecting adherence to prescription medication based the identification of several motions using the built-in tri-axial accelerometers and gyroscopes. The efficacy of the proposed technique is confirmed through a survey of medication ingestion habits and experimental results on movement classification.

Exergaming as a tool to combat obesity yields an interesting take on the problem of design and implementation of activity recognition systems for truly mobile games that achieve moderate levels of intensity. This work presents SoccAR, a mobile, sensor-based wearable exergaming system with fine-grain activity recognition. The system in this paper presents a recognition algorithm for the appropriate classification of 26 movements by extracting a large number of features and selecting the most important, as well as developing a multiple model strategy to better classify movements. This movement strategy allows for a trade off of detailed classification versus classification speed. A metric to define the accuracy in terms of the importance of particular movements is defined. The scheme presented develops a framework for more accurately classifying movements with a smaller number of features for a large, multiclass real-time environment. This results in a more accurate classification of movements, with an F-score in cross-validation of .937 using a PUK-kernel based SVM and multiple models, to .755 using only a single RBF-based model and 20 features.

Wireless health systems enable remote and continuous monitoring of individuals, with applications in elderly care support, chronic disease management, and preventive care. The underlying sensing platform provides constructs that consider the quality of information driven from the system and ensure the reliability/validity of the outcomes to support the decision-making processes. In this paper, we present an approach to integrate contextual information within the data processing flow in order to improve the quality of measurements. We focus on a pilot application that uses wearable motion sensors to calculate metabolic equivalent of task (MET) of exergaming movements. Exergames need to show energy expenditure values, often using accelerometer approximations applied to general activities. We focus on two contextual factors, namely “activity type” and “sensor location,” and demonstrate how these factors can be used to enhance the measured values, since allocating larger weights to more informative sensors can improve the final measurements. Further, designing regression models for each activity provides better results than any generalized model. Indeed, the averaged R2 value for the movements using simple sensor location improve from a general 0.71 to as high as 0.84 for an individual activity type. The different methods present a range of R2 value averages across activity type from 0.64 for sensor location to 0.89 for multidimensional regression, with an average game play MET value of 7.93. Finally, in a leaveone-subject-out cross validation, a mean absolute error of 2.231 METs is found when predicting the activity levels using the best models.

Remote health monitoring (RHM) has emerged as a solution to help reduce the cost burden of unhealthy lifestyles and aging populations. Enhancing compliance to prescribed medical regimens is an essential challenge to many systems, even those using smartphone technology. In this paper, we provide a technique to improve smartphone battery consumption and examine the effects of smartphone battery lifetime on compliance, in an attempt to enhance users' adherence to remote monitoring systems. We deploy WANDA-CVD, an RHM system for patients at risk of cardiovascular disease (CVD), using a wearable smartphone for detection of physical activity. We tested the battery optimization technique in an in-lab pilot study and validated its effects on compliance in the Women's Heart Health Study. The battery optimization technique enhanced the battery lifetime by 192% on average, resulting in a 53% increase in compliance in the study. A system like WANDA-CVD can help increase smartphone battery lifetime for RHM systems monitoring physical activity.

The ability to continuously monitor respiration rates of patients in homecare or in clinics is an important goal. Past research showed that monitoring patient breathing can lower the associated mortality rates for long-term bedridden patients. Nowadays, in-bed sensors consisting of pressure sensitive arrays are unobtrusive and are suitable for deployment in a wide range of settings. Such systems aim to extract respiratory signals from time-series pressure sequences. However, variance of movements, such as unpredictable extremities activities, affect the quality of the extracted respiratory signals. BreathSens, a high-density pressure sensing system made of e-Textile, profiles the underbody pressure distribution and localizes torso area based on the high-resolution pressure images. With a robust bodyparts localization algorithm, respiratory signals extracted from the localized torso area are insensitive to arbitrary extremities movements. In a study of 12 subjects, BreathSens demonstrated its respiratory monitoring capability with variations of sleep postures, locations, and commonly tilted clinical bed conditions.

Wearable sensory devices are becoming the enabling technology for many applications in healthcare and well-being, where computational elements are tightly coupled with the human body to monitor specific events about their subjects. Classification algorithms are the most commonly used machine learning modules that detect events of interest in these systems. The use of accurate and resource-efficient classification algorithms is of key importance because wearable nodes operate on limited resources on one hand and intend to recognize critical events (e.g., falls) on the other hand. These algorithms are used to map statistical features extracted from physiological signals onto different states such as health status of a patient or type of activity performed by a subject. Conventionally selected features may lead to rapid battery depletion, mainly due to the absence of computing complexity criterion while selecting prominent features. In this paper, we introduce the notion of power-aware feature selection, which aims at minimizing energy consumption of the data processing for classification applications such as action recognition. Our approach takes into consideration the energy cost of individual features that are calculated in real-time. A graph model is introduced to represent correlation and computing complexity of the features. The problem is formulated using integer programming and a greedy approximation is presented to select the features in a power-efficient manner. Experimental results on thirty channels of activity data collected from real subjects demonstrate that our approach can significantly reduce energy consumption of the computing module, resulting in more than 30 percent energy savings while achieving 96.7 percent classification accuracy.

In remote health monitoring of patient's physical activity, ensuring correctness and authenticity of the received data is essential. Although many activity monitoring systems, devices and techniques have been developed, preventing patient cheating of an activity monitor has been a primarily unaddressed challenge across the board. Patients can manually shake an activity monitor device (sensor) with their hand and watch their physical activity points or rewards increase, we define this as "self-inflicted" cheating. A second type of cheating, "impersonator" cheating, is when subjects hand the activity sensor over to a friend or second party to wear and perform physical activity on their behalf. In this paper, we propose two novel methods based on classification algorithms to address the cheating problems. The first classification framework improves the correctness of our data by detecting self-inflicted cheatings. The second technique is an advanced classification scheme that extracts and learns unique patient-specific activity patterns from prior data collected on a patient to distinguish the true subject from an impersonator. We tested our proposed techniques on Wanda, a remote health monitoring system used in our Women's Heart Health study of 90 African American women at risk of cardiovascular disease. We were able to distinguish cheating from other physical activities such as walking and running, as well as other common activities of daily living such as driving and playing video games. The self-inflicted cheating classifier achieved an accuracy of above 90% and an AUC of 99%. The impersonator cheater framework results in an average accuracy of above 90% and an average AUC of 94%. Our results provide insight into the randomness of cheating activities, successfully detects cheaters, and attempts to build more context-aware remote activity monitors that more accurately capture patient activity.

Maintaining appropriate levels of food intake anddeveloping regularity in eating habits is crucial to weight lossand the preservation of a healthy lifestyle. Moreover, maintainingawareness of one's own eating habits is an important steptowards portion control and ultimately, weight loss. Though manysolutions have been proposed in the area of physical activitymonitoring, few works attempt to monitor an individual's foodintake by means of a noninvasive, wearable platform. In thispaper, we introduce a novel nutrition-intake monitoring systembased around a wearable, mobile, wireless-enabled necklacefeaturing an embedded piezoelectric sensor. We also propose aframework capable of estimating volume of meals, identifyinglong-term trends in eating habits, and providing classificationbetween solid foods and liquids with an F-Measure of 85% and86% respectively. The data is presented to the user in the formof a mobile application.

Due to the exploding costs of chronic diseasesstemming from physical inactivity, wearable sensor systems toenable remote, continuous monitoring of individuals has increasedin popularity. Many research and commercial systems exist inorder to track the activity levels of users from general dailymotion to detailed movements. This work examines this problemfrom the space of smartwatches, using the Samsung GalaxyGear, a commercial device containing an accelerometer and agyroscope, to be used in recognizing physical activity. This workalso shows the sensors and features necessary to enable suchsmartwatches to accurately count, in real-time, the repetitions offree-weight and body-weight exercises. The goal of this work isto try and select only the best single axis for each activity byextracting only the most informative activity-specific features, inorder to minimize computational load and power consumptionin repetition counting. The five activities are incorporated in aworkout routine, and knowing this information, a random forestclassifier is built with average area under the curve (AUC) of: 974, with average accuracy of 93%, in cross validation to identify eachrepetition of a given exercise using all available sensors and AUCof: 950 with accuracy of 89:9% using the single best axis foreach activity alone. Adding a gyroscope with the accelerometerincreased the average AUC from: 968 to: 974, increasing theaccuracy of specific movements as much as 2%. Results show that, while a combination of accelerometer and gyroscope provide thestrongest classification results, often times features extracted froma single, best axis are enough to accurately identify movementsfor a personal training routine, where that axis is often, but notalways, an accelerometer axis.

With our approach, for the synthesis and energy-efficient operation of a pressure sensor-based soft keyboard, energy is optimized at five levels of abstraction: 1) architecture of sensor systems, 2) sensing schedule, 3) sensor data processing, 4) use of semantic information, and 5) customization. We have been able to achieve up to a factor of 63 energy reduction in a keyboard case study over the standard using various techniques. For example, when each sensor senses several keyboard events and each event is sensed by three sensors, sensing and data processing results in a 12- to 42-fold energy savings depending on typing speeds. Customization techniques accounting for user typing speed and duration of typing pulses support another 1.5-fold savings. We demonstrate using a proof of concept prototype evaluation with five participants.

Detecting human activity independent of intensity is essential in many applications, primarily in calculating metabolic equivalent rates and extracting human context awareness. Many classifiers that train on an activity at a subset of intensity levels fail to recognize the same activity at other intensity levels. This demonstrates weakness in the underlying classification method. Training a classifier for an activity at every intensity level is also not practical. In this paper, we tackle a novel intensity-independent activity recognition problem where the class labels exhibit large variability, the data are of high dimensionality, and clustering algorithms are necessary. We propose a new robust stochastic approximation framework for enhanced classification of such data. Experiments are reported using two clustering techniques, K-Means and Gaussian Mixture Models. The stochastic approximation algorithm consistently outperforms other well-known classification schemes which validate the use of our proposed clustered data representation. We verify the motivation of our framework in two applications that benefit from intensity-independent activity recognition. The first application shows how our framework can be used to enhance energy expenditure calculations. The second application is a novel exergaming environment aimed at using games to reward physical activity performed throughout the day, to encourage a healthy lifestyle.

PeopleN EURODEGENERATIVE diseases are progressive and difficult to diagnose in their early stages.Progressive impairment in the activities of daily living, as well as cognitive deterioration, leads to an increase in patient's dependence.Neuropsychiatric symptoms are common features and include psychosis (delusions and hallucinations), depressive mood, anxiety, irritability/lability, apathy, euphoria, disinhibition, agitation/aggression, aberrant motor activities, sleep disturbance, and eating disorders.Additionally, patients have a tendency to wander and misplace objects in their environment.Therefore, cognitive impaired patients need constant monitoring to ensure their wellbeing, and that they do not harm themselves.Ambient intelligence (AmI) is the computing paradigm that can provide support both for cognitive impaired people within their domestic environments and for clinicians to collect data needed to assess the disease.A novel class of applications can potentially emerge from the specialization of AmI technologies to the special domain of cognitive impaired users.However, such applications must be able to deal with peculiarities due to irrational and abnormal behaviors of cognitive impaired people within their environments, and their general attitude to not accepting wearable technologies.Several technical challenges remain to be solved before effective, intelligent, secure, and reliable AmI applications for the support of cognitive impaired people can be deployed trustfully into real environments.In this special section, the paper "The role of Virtual Motor Rehabilitation.A quantitative analysis between Acute and Chronic Patients with acquired brain injury," concerning acquired brain injury, compares the evolution of chronic patients with acute patients in a virtual rehabilitation program.For this study authors have developed a "Vestibular Virtual Rehabilitation" system.Results have shown a similar recovery for chronic and acute patients during the period of intervention.It has also been shown that chronic patients stop their improvement when they finish the training encouraging the migration of such rehabilitation technologies to home.In the contribution "An Adaptable and Flexible Framework for Assistive Living of Cognitively Impaired People" describes guidelines and an adaptable framework for the dynamic integration of assistive services with their related sensing technologies and interaction devices.The paper on "Statistical Anomaly Detection for Individuals with Cognitive Impairments" focuses on the identification of anomalies for users' routes, which may be useful to assist the impaired in case of losing one's way or to alert caregivers in case of wandering.The proposed approach relies on the exploitation Digital Object

Physical rehabilitation is an important process for patients recovering after surgery. In this paper, we propose and develop a framework to monitor on-bed range of motion exercises that allows physical therapists to evaluate patient adherence to set exercise programs. Using a dense pressure sensitive bedsheet, a sequence of pressure maps are produced and analyzed using manifold learning techniques. We compare two methods, Local Linear Embedding and Isomap, to reduce the dimensionality of the pressure map data. Once the image sequences are converted into a low dimensional manifold, the manifolds can be compared to expected prior data for the rehabilitation exercises. Furthermore, a measure to compare the similarity of manifolds is presented along with experimental results for five on-bed rehabilitation exercises. The evaluation of this framework shows that exercise compliance can be tracked accurately according to prescribed treatment programs.

Cardiovascular disease (CVD) is a major issue to public health. It contributes 41% to the Chinese death rate each year. This huge loss encouraged us to develop a Wearable Efficient teleCARdiology systEm (WE-CARE) for early warning and prevention of CVD risks in real time. WE-CARE is expected to work 24/7 online for mobile health (mHealth) applications. Unfortunately, this purpose is often disrupted in system experiments and clinical trials, even if related enabling technologies work properly. This phenomenon is rooted in the overload issue of complex Electrocardiogram (ECG) data in terms of system integration. In this study, our main objective is to get a system light-loading technology to enable mHealth with a benchmarked ECG anomaly recognition rate. To achieve this objective, we propose an approach to purify clinical features from ECG raw data based on manifold learning, called the Manifold-based ECG-feature Purification algorithm. Our clinical trials verify that our proposal can detect anomalies with a recognition rate of up to 94% which is highly valuable in daily public health-risk alert applications based on clinical criteria. Most importantly, the experiment results demonstrate that the WE-CARE system enabled by our proposal can enhance system reliability by at least two times and reduce false negative rates to 0.76%, and extend the battery life by 40.54%, in the system integration level.

Exergaming is expanding as an option for sedentary behavior in childhood/adult obesity and for extra exercise for gamers. This paper presents the development process for a mobile active sports exergame with near-realistic motions through the usage of body-wearable sensors. The process begins by collecting a dataset specifically targeted to mapping real-world activities directly to the games, then, developing the recognition system in a fashion to produce an enjoyable game. The classification algorithm in this paper has precision and recall of 77% and 77% respectively, compared with 40% and 19% precision and recall on current activity monitoring algorithms intended for general daily living activities. Aside from classification, the user experience must be strong enough to be a successful system for adoption. Indeed, fast and intense activities as well as competitive, multiplayer environments make for a successful, enjoyable exergame. This enjoyment is evaluated through a 30 person user study. Multiple aspects of the exergaming user experience trials have been merged into a comprehensive survey, called ExerSurvey. All but one user thought the motions in the game were realistic and difficult to cheat. Ultimately, a game with near-realistic motions was shown to be an enjoyable, active video exergame for any environment.

The nine papers in this special issue cover multiple aspects of emerging wireless body area networks (WBANs) for ubiquitous healthcare.

Detecting human activity independent of intensity is essential in many applications, primarily in calculating metabolic equivalent rates (MET) and extracting human context awareness from on-body inertial sensors. Many classifiers that train on an activity at a subset of intensity levels fail to classify the same activity at other intensity levels. This demonstrates weakness in the underlying activity model. Training a classifier for an activity at every intensity level is also not practical. In this paper we tackle a novel intensity-independent activity recognition application where the class labels exhibit large variability, the data is of high dimensionality, and clustering algorithms are necessary. We propose a new robust Stochastic Approximation framework for enhanced classification of such data. Experiments are reported for each dataset using two clustering techniques, K-Means and Gaussian Mixture Models. The Stochastic Approximation algorithm consistently outperforms other well-known classification schemes which validates the use of our proposed clustered data representation.

Hyperexcitability in hand is a disorder characterized by exaggerated muscle movement, and is a common symptom associated with neuro-degenerative diseases and spinal cord injuries. Current assessment methods for hyperexcitability rely on subjective examination, or on methods that evaluate the overall hand grip performance without particularization in the excitation. This paper introduces a system that utilizes an inexpensive body sensor device combined with a series of signal processing units that extract information specifically related to physiological phenomena generated by hyperexcitability. A clinical cohort study has been conducted on nine patients with cervical spinal cord injuries (mean age 58.2 ± 13.5). The experimental results show that the proposed signal processing mechanism accurately detects and analyzes the body signal. The medical significance of the experimental results is also investigated. This opens up a new opportunity for patients and clinical professionals to obtain accurate feedback of patient's motor function in an economical and ubiquitous manner.

This paper presents the design of an on-bed rehabilitation exercise monitoring system that utilizes a high density sensor bedsheet to evaluate active range of motion exercises. We propose and develop a novel framework to analyze the progression of pressure image sequences using manifold learning. The image sequences are reduced to a low dimensional subspace that can be measured against expected prior data for each of the rehabilitation exercises. We also present a metric to compare manifold similarities. Our experimental results on five on-bed exercises show that this system can accurately track compliance of patients to prescribed treatment programs. It allows physical therapists to evaluate how well patients adhere to the rehabilitation exercises. The system is convenient to setup, unobtrusive, and can be used for reliable, long term monitoring.

This paper presents the design of an on-bed rehabilitation exercise monitoring system that utilizes a high density sensor bedsheet to evaluate active range of motion exercises. We propose and develop a novel framework to analyze the progression of pressure image sequences using manifold learning. The image sequences are reduced to a low dimensional subspace that can be measured against expected prior data for each of the rehabilitation exercises. We also present a metric to compare manifold similarities. Our experimental results on five on-bed exercises show that this system can accurately track compliance of patients to prescribed treatment programs. It allows physical therapists to evaluate how well patients adhere to the rehabilitation exercises. The system is convenient to setup, unobtrusive, and can be used for reliable, long term monitoring.

Although most of the medical and healthcare monitoring systems generate multi-dimensional time series (via multiple sensors), most of the work by research community has been focused on defining distance metrics and matching algorithms to improve accuracy and optimize performance of search in single dimensional time series. In this work we motivate the need for multidimensional time series matching and propose a scalable technique that has high accuracy in presence of noise, uncertainty, and lack of synchronization between dimensions. We focus on two medical monitoring devices and their applications to showcase the advantages, performance, and accuracy of our multi-dimensional time series search technique. We demonstrate effectiveness of our signal search technique by using precision and recall metrics.

Although most of the medical and healthcare monitoring systems generate multi-dimensional time series (via multiple sensors), most of the work by research community has been focused on defining distance metrics and matching algorithms to improve accuracy and optimize performance of search in single dimensional time series. In this work we motivate the need for multidimensional time series matching and propose a scalable technique that has high accuracy in presence of noise, uncertainty, and lack of synchronization between dimensions. We focus on two medical monitoring devices and their applications to showcase the advantages, performance, and accuracy of our multi-dimensional time series search technique. We demonstrate effectiveness of our signal search technique by using precision and recall metrics.

The use of accelerometers to approximate energy expenditure and serve as inputs for exergaming, have both increased in prevalence in response to the worldwide obesity epidemic. Exergames have a need to show energy expenditure values to validate their results, often using accelerometer approximations applied to general daily-living activities. This work presents a method for estimating the metabolic equivalent of task (MET) values achieved when users perform exergaming-specific movements. This shows the caloric expenditure achieved by active video games, based upon raw gravity values of accelerations. Results show that, while a fusion of sensors monitoring the entire body achieves the best results, sensors placed closest to the primary location of movement achieve the most accurate approximations to the METs achieved per activity as well as the overall MET achieved for the soccer exergame under consideration. The METs achieved approach 7, the value considered to be actual casual soccer game play.

Recently Electronic Textile (E-Textile) technology enables the weaving computation and communication components into the clothes that we wear and objects that we interact with every day. E-Textile enables the design and development of a broad range of pervasive sensing systems such as smart bed sheets for sleep posture monitoring, insoles in medical shoes for monitoring plantar pressure distribution, smart garments and sensing gloves. However the low cost of E-Textiles come at the cost of accuracy. In this work we propose an actuator-based method that increases the accuracy of E-Textiles by means of enabling real-time calibration. Our proposed system increases system accuracy by 38.55% on average (maximum 58.4%).

Sleep plays a pivotal role in the quality of life, and sleep posture is related to many medical conditions such as sleep apnea. In this paper, we design a dense pressure-sensitive bedsheet for sleep posture monitoring. In contrast to existing techniques, our bedsheet system offers a completely unobtrusive method using comfortable textile sensors. Based on high-resolution pressure distributions from the bedsheet, we develop a novel framework for pressure image analysis to monitor sleep postures, including a set of geometrical features for sleep posture characterization and three sparse classifiers for posture recognition. We run a pilot study and evaluate the performance of our methods with 14 subjects to analyze 6 common postures. The experimental results show that our proposed method enables reliable sleep posture recognition and offers better overall performance than state-of-the-art methods, achieving up to 83.0% precision and 83.2% recall on average.

No abstract available.

We introduce Hermes , a lightweight smart shoe and its supporting infrastructure aimed at extending gait and instability analysis and human instability/balance monitoring outside of a laboratory environment. We aimed to create a scientific tool capable of high-level measures, by combining embedded sensing, signal processing and modeling techniques. Hermes monitors walking behavior and uses an instability assessment model to generate quantitative value with episodes of activity identified by physician, researchers or investigators as important. The underlying instability assessment model incorporates variability and correlation of features extracted during ambulation that have been identified by geriatric motion study experts as precursor to instability, balance abnormality and possible fall risk. Hermes provides a mobile, affordable and long-term instability analysis and detection system that is customizable to individual users, and is context-aware, with the capability of being guided by experts. Our experiments demonstrate the feasibility of our model and the complimentary role our system can play by providing long-term monitoring of patients outside a hospital or clinical setting at a reduced cost, with greater user convenience, compliance and inference capabilities that meet the physician's or investigator's needs.

With the growing cost associated with the diagnosis and treatment of chronic neuro-degenerative diseases, the design and development of portable monitoring systems becomes essential. Such portable systems will allow for early diagnosis of motor function ability and provide new insight into the physical characteristics of ailment condition. This paper introduces a highly mobile and inexpensive monitoring system to quantify upper-limb performance for patients with movement disorders. With respect to the data analysis, we first present an approach to quantify general motor performance using the introduced sensing hardware. Next, we propose an ailment-based analysis which employs a significant-feature identification algorithm to perform cross-patient data analysis and classification. The efficacy of the proposed framework is demonstrated using real data collected through a clinical trial. The results show that the system can be utilized as a preliminary diagnostic tool to inspect the level of hand-movement performance. The ailment-based analysis performs an intergroup comparison of physiological signals for cerebral vascular accident (CVA) patients, chronic inflammatory demyelinating polyneuropathy (CIDP) patients, and healthy individuals. The system can classify each patient group with an accuracy of up to 95.00% and 91.42% for CVA and CIDP, respectively.

Wearable sensing systems have recently enabled a variety of medical monitoring and diagnostic applications in wireless health. The need for multiple sensors and constant monitoring leads these systems to be power hungry and expensive with short operating lifetimes. We introduce a novel methodology that takes advantage of contextual and semantic properties in human behavior to enable efficient design and optimization of such systems from the data and information point of view. This, in turn, directly influences the wireless communication and local processing power consumption. We exploit intrinsic space and temporal correlations between sensor data while considering both user and system contextual behavior. Our goal is to select a small subset of sensors that accurately capture and/or predict all possible signals of a fully instrumented wearable sensing system. Our approach leverages novel modeling, partitioning, and behavioral optimization, which consists of signal characterization, segmentation and time shifting, mutual signal prediction, and a simultaneous minimization composed of subset sensor selection and opportunistic sampling. We demonstrate the effectiveness of the technique on an insole instrumented with 99 pressure sensors placed in each shoe, which cover the bottom of the entire foot, resulting in energy reduction of 72% to 97% for error rates of 5% to 17.5%.

Time series subsequence matching (or signal searching) has importance in a variety of areas in health care informatics. These areas include case-based diagnosis and treatment as well as the discovery of trends and correlations between data. Much of the traditional research in signal searching has focused on high dimensional R-NN matching. However, the results of R-NN are often small and yield minimal information gain; especially with higher dimensional data. This paper proposes a randomized Monte Carlo sampling method to broaden search criteria such that the query results are an accurate sampling of the complete result set. The proposed method is shown both theoretically and empirically to improve information gain. The number of query results are increased by several orders of magnitude over approximate exact matching schemes and fall within a Gaussian distribution. The proposed method also shows excellent performance as the majority of overhead added by sampling can be mitigated through parallelization. Experiments are run on both simulated and real-world biomedical datasets.

The Wolf Motor Function Test (WMFT), which involves real time timing measurements, is used to define the functional ability of the paretic limb of post stroke patients. The accuracy and consistency of the timing results are crucial for scoring, while manual stopwatch measuring introduces mistakes and uncertainty. A technique which uses camera and sensors to automate the test and achieve accurate results is proposed here. This system measures time for seven tasks with a monitor camera and a Xilinx Virtex II Pro Field Programmable Gate Array (FPGA). The FPGA was mainly chosen for its better performance compared to general purpose System on Chip (SoC) for computational intensive tasks, such as image processing in this system. The accuracy of the system has been validated in a user study on selected WMFT tasks with ground truth time measurement obtained from pressure sensors. Suggestions are also given on how the framework can be adapted to the remaining tasks.

ECG analysis is universal and important in miscellaneous medical applications. However, high computation complexity is a problem which has been shown in several levels of conventional data mining algorithms for ECG analysis. In this paper, we presented a novel manifold approach to visualize and analyze the ECG signal. According to regularity of the data, our algorithm can discover the intrinsic structure and represent the streaming data with a 1-D manifold on a 2-D space. Furthermore, the proposed algorithm can reliably detect the anomaly in ECG streaming data. We evaluated the performance of the algorithm with two different anomalies in wearable applications: for the anomaly from heart disorders such as apnea, arrythmia, our algorithm could achieve up to 90% recognition rate, for the anomaly from the ECG device, our algorithm could detect the outlier with 100%.

Human activity monitoring, through the use of body-wearable sensors, allows for many exciting possibilities, from gaming, to exercise, to preventative health care, where childhood obesity is a growing epidemic. The rapidly increasing nature of this trend requires serious thought at targeting its causes and finding solutions. One major influence is video gaming and the hours of sedentary behavior associated with it. In this paper, we present our system for enforcing physical activity of humans playing video games with our body-worn sensor system as the controller. Body movements are communicated with the host computer that calculates physical activity via the metabolic equivalent of task, and runs signal processing algorithms to classify and enforce movements. A user study was conducted to validate the effectiveness and realism of the system while playing an actual video game and data was collected from these same users in order to verify the accuracy of our system. The results show a system that not only allows physical activity, but also enforces it, leading to healthier gaming and accurate motion analysis.

Human activity recognition using wearable body sensors is playing a significant role in ubiquitous and mobile computing. One of the issues related to this wearable technology is that the captured activity signals are highly dependent on the location where the sensors are worn on the human body. Existing research work either extracts location information from certain activity signals or takes advantage of the sensor location information as a priori to achieve better activity recognition performance. In this paper, we present a compressed sensing-based approach to co-recognize human activity and sensor location in a single framework. To validate the effectiveness of our approach, we did a pilot study for the task of recognizing 14 human activities and 7 on body-locations. On average, our approach achieves an 87:72% classification accuracy (the mean of precision and recall).

In this paper, we present a mechanism for estimating data quality of BANs composed of cardiac sensors. Currently available cardiac monitoring sensors suffer from high level of noise generated from loose physical contact of the sensor node due to the highly mobile and pervasive environment of the BAN (e.g., at-home remote health care applications). Therefore, there is a need to estimate the data quality of individual cardiac sensors as well as the data quality of the overall BAN while particularly considering the resource scarceness of BAN-scale mobile systems. The proposed method successfully estimates the data quality of a BAN without employing computationally expensive machine learning techniques. It also provides a number of resource management options that enable efficient data quality estimation. We present experimental results of four participants with three off-the-shelf cardiac sensors to form a BAN. We also present simulation results to examine if the proposed mechanism can successfully detect health hazardous events such as heart arrhythmia.

Many wearable embedded systems benefit from classification algorithms where statistical features extracted from physiological signals are mapped onto different user's states such as health status of a patient or type of activity performed by a subject. Conventionally selected features lead to rapid battery depletion in these battery-operated systems, mainly due to the absence of computing complexity criterion while selecting prominent features. In this paper, we introduce the notion of power-aware feature selection, which minimizes energy consumption of the signal processing for classification applications. Our approach takes into consideration the energy cost of individual features that are calculated in real-time. The problem is formulated using integer programming and a greedy approximation is presented to select the features in a power-efficient manner. Experimental results on thirty channels of activity data demonstrate that our approach can significantly reduce energy consumption of the computing module resulting in more than 30$% energy savings while achieving 96.7% classification accuracy.

No abstract available.

3-D vision technologies are extensively used in a wide variety of applications. Particularly glasses-based 3-D technology facilities are increasingly becoming affordable to our daily lives. Considering health issues raised by 3-D video technologies, to the best of our knowledge, most of the pilot studies are practiced in a highly-controlled laboratory environment only. In this paper, we present NeuroGlasses, a nonintrusive wearable physiological signal monitoring system to facilitate health analysis and diagnosis of 3-D video watchers. The NeuroGlasses system acquires health-related signals by physiological sensors and provides feedbacks of health-related features. Moreover, the NeuroGlasses system employs signal-specific reconstruction and feature extraction to compensate the distortion of signals caused by variation of the placement of the sensors. We also propose a server-based NeuroGlasses infrastructure where physiological features can be extracted for real-time response or collected on the server side for long term analysis and diagnosis. Through an on-campus pilot study, the experimental results show that NeuroGlasses system can effectively provide physiological information for healthcare purpose. Furthermore, it approves that 3-D vision technology has a significant impact on the physiological signals, such as EEG, which potentially leads to neural diseases.

The most challenging problem in the current block-based statistical static timing analysis (SSTA) is how to handle the max operation efficiently and accurately. Existing SSTA techniques suffer from limited modeling capability by using a linear delay model with Gaussian distribution, or have scalability problems due to expensive operations involved to handle non-Gaussian variation sources or nonlinear delays. To overcome these limitations, we propose efficient algorithms to handle the max operation in SSTA with both quadratic delay dependency and non-Gaussian variation sources simultaneously. Based on such algorithms, we develop an SSTA flow with quadratic delay model and non-Gaussian variation sources. All the atomic operations, max and add, are calculated efficiently via either closed-form formulas or low dimension (at most 2-D) lookup tables. We prove that the complexity of our algorithm is linear in both variation sources and circuit sizes, hence our algorithm scales well for large designs. Compared to Monte Carlo simulation for non-Gaussian variation sources and nonlinear delay models, our approach predicts the mean, standard deviation and 95% percentile point with less than 2% error, and the skewness with less than 10% error.

Sitting posture analysis is critical for daily applications in biomedical, education and healthcare fields. However, it remains unclear how to monitor sitting posture economically and comfortably. To this end, we presented an eTextile device, called eCushion, in this paper, which can analyze the sitting posture of human being accurately and non-invasively. First, we discussed the implementation of eCushion and design challenges of sensing data, such as scale, offset, rotation and crosstalk. Then, several effective techniques have been proposed to improve the recognition rate of sitting posture. Our experimental results show that the recognition rate of our eCushion system could achieve 92% for object-oriented cases and 79% for general cases.

We present a technique to discover the position of sensors on the human body. Automatic on-body device localization ensures correctness and accuracy of measurements in health and medical monitoring systems. In addition, it provides opportunities to improve the performance and usability of ubiquitous devices. Our technique uses accelerometers to capture motion data to estimate the location of the device on the user's body, using mixed supervised and unsupervised time series analysis methods. We have evaluated our technique with extensive experiments on 25 subjects. On average, our technique achieves 89% accuracy in estimating the location of devices on the body.

We target body-wearable sensor networks, in which sensor nodes are strategically placed on the human body and the wireless communications are conducted on/off the surface of the body. The results, obtained by performing multiple experiments in outdoor environments, are presented. A single on body transmitter communicates with a single receiver node, which is located on the body or off the body at various distances. Sensor nodes utilized in our experiments are equipped with XBee and XBee Pro wireless modules for on body and off body communications, respectively. The focus of our work is to observe how the Received Signal Strength (RSS) and the Packet Reception Rate (PRR) vary as we change the communication distance and transmission power level. Our experimental results can be used to perform transmission power control with high precision in order not to exceed a certain packet error rate.

Social system networks with high data rates and limited storage will discard data if the system cannot connect and upload the data to a central server. We address the challenge of limited storage capacity in mobile health systems during network partitions with a heuristic that achieves efficiency in storage capacity by modifying the granularity of the medical data during long intercontact periods. Patterns in the connectivity, reception rate, distance, and location are extracted from the social system network and leveraged in the global algorithm and online heuristic. In the global algorithm, the stochastic nature of the data is modeled with maximum likelihood estimation based on the distribution of the reception rates. In the online heuristic, the correlation between system position and the reception rate is combined with patterns in human mobility to estimate the intracontact and intercontact time. The online heuristic performs well with a low data loss of 2.1%-6.1%.

Abstract This paper presents an energy‐efficient and coverage‐preserving communication protocol which distributes a uniform energy load to the sensors in a wireless microsensor network. This protocol, called Distance‐based Segmentation (DBS), is a cluster‐based protocol that divides the entire network into equal‐area segments and applies different clustering policies to each segment to (1) reduce total energy dissipation and (2) balance the energy load among the sensors. Therefore, it prolongs the lifetime of the network and improves the sensing coverage. Moreover, the proposed routing protocol does not need any centralized support from a certain node which is at odds with aiming to establish a scalable communication protocol. Results from extensive simulations on two different network configurations show that by lowering the number of wasteful transmissions in the network, the DBS can achieve as much as a 20% reduction in total dissipated energy as compared with current cluster‐based protocols. In addition, this protocol is able to distribute energy load more evenly among the sensors in the network. Hence, it yields up to a 66% increase in the useful network lifetime. According to the simulation results, the sensing coverage degradation of the DBS is considerably slower than that of the other cluster‐based protocols. Copyright © 2009 John Wiley & Sons, Ltd.

We present a method for unsupervised discovery of abnormal occurrences of activities in multi-dimensional time series data. Unsupervised activity discovery approaches differ from traditional supervised methods in that there is no requirement for manually labeled training datasets. In addition, they minimize the need for field experts' knowledge during the setup phases, which makes the deployment phase faster and simpler. We focus our attention on wearable computing systems and their applications in human activity monitoring for health care and medicine. The developed method constructs activity models in multi-dimensional time series based on the frequency and coincidence of activity perceptual primitives in single-dimensional time series data. We study the frequent variations exposed in human activity time series data and leverage physical attributes of the data to classify the activity primitives. A graph clustering approach is used to construct the frequent activity structures. Such structures are used to locate normal and abnormal occurrences of activities in time series. A method is presented to distinguish the abnormal activity occurrences from the normal occurrences. Two state-of-the-art wearable embedded systems (Smartcane and Smartshoe) are used to perform empirical evaluation of the developed methods.

Multi-Vdd techniques enable application of lower supply voltage levels on cells with timing slacks. New voltage assignment, placement and voltage island partitioning methods are needed for better utilization of this technology. Our experiments show that in order to have an effective post placement voltage island generation we need to directly consider the energy consumption overhead of the level shifters. We first model the level shifter aware post placement voltage assignment as a 0-1 quadratic programming problem and show that it can be solved in linear time using a 0.879-approximation algorithm. Also, for rectangular voltage island generation we propose an exact modified algorithm as well as a heuristic algorithm both involving the overhead of the level shifters in their cost functions. While the modified algorithm results in better power saving the heuristic algorithm runs with lower time complexity with marginal loss in the quality.

Heart failure is a leading cause of death in the United States, with around 5 million Americans currently suffering from congestive heart failure. The WANDA B. wireless health technology leverages sensor technology and wireless communication to monitor heart failure patient activity and to provide tailored guidance. Patients who have cardiovascular system disorders can measure their weight, blood pressure, activity levels, and other vital signs in a real-time automated fashion. The system was developed in conjunction with the UCLA Nursing School and the UCLA Wireless Health Institute for use on actual patients. It is currently in use with real patients in a clinical trial.

No abstract available.

Depression is one of the leading causes of disability. Methods are needed to quantitatively classify emotions in order to better understand and treat mood disorders. This research proposes techniques to improve communication in body sensor network (BSN) that gathers data on the affective states of the patient. These BSNs can continuously monitor, discretely quantify, and classify a patient's depressive states. In addition, data on the patient's lifestyle can be correlated with his/her physiological conditions to identify how various stimuli trigger symptoms. This continuous stream of data is an improvement over a snapshot of localized symptoms that a doctor often collects during a medical examination. Our research first quantifies how the body interferes with communication in a BSN and detects a pattern between the line of sight of an embedded device and its reception rate. Then, a mathematical model of the data using linear programming techniques determines the optimal placement and number of sensors in a BSN to improve communication. Experimental results show that the optimal placement of embedded devices can reduce power cost up to 27% and reduce hardware costs up to 47%. This research brings researchers a step closer to continuous, real-time systemic monitoring that will allow one to analyze the dynamic human physiology and understand, diagnosis, and treat mood disorders.

We present an optimal methodology for dynamic voltage scheduling problem in the presence of realistic assumption such as leakage-power and intra-task overheads. Our contribution is an optimal algorithm for energy minimization that concurrently assumes the presence of (1) non-convex energy-speed models as opposed to previously studied convex models, (2) discrete set of operational modes (voltages) and (3) intra-task energy and delay overhead. We tested our algorithm on MediaBench and task sets used in previous papers. Our simulation results show an average of 22% improvement in energy reduction in comparison with optimal algorithms for convex models without switching overhead and on average of 24% with consideration for energy and delay overheads. This analysis lays the groundwork for improving functionality in CAD design through non-convex techniques for discrete models.

We explore the link scheduling optimization problem in the context of scalable in-network data aggregation, extending results for broadcast networks to routing in general networks. The primary vehicle for resource preservation is transmission suppression. For certain types of queries, nodes can avoid transmitting records if they can locally infer that their data is not needed to execute the query. We introduce a novel protocol paradigm for duplicate-insensitive exemplary monotonic (e.g. MIN and MAX) data aggregation queries. Performance of query execution in these networks is measured through collective expected number of transmissions in the network, and is linked to the minimum and maximum connectivity (delta, Delta) of nodes in general graphs. Nodes can reduce transmissions and save power by forcibly broadcasting partial results to the network during data collection. An algorithm running in time O(nm) is presented which achieves O((n In n In Delta)/delta) expected transmissions.

This article presents an efficient technique for placement and routing of sensors/actuators and processing units in a grid network. The driver application that we present is a medical jacket, which requires an extremely high level of robustness and fault tolerance. The power consumption of such jacket is another key technological constraint. Our proposed interconnection network is a mesh of wires. A jacket made of fabric and wires would be susceptible to accidental damage via tears. By modeling the tears, we evaluate the probability of having failures on every segment of wires in our mesh interconnection network. Then, we study two problems of placement and routing in the sensor networks such that the fault tolerance is maximized while the power consumption is minimized. We develop efficient integer linear programming (ILP) formulations to address these problems and perform both placement and routing, simultaneously. This ensures that the solution is a lower bound for both problems. We evaluate the effectiveness of our proposed techniques on a variety of benchmarks.

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.

The improvement in processor performance through continuous breakthroughs in transistor technology has resulted in the proliferation of lightweight embedded systems. Advances in wireless technology and embedded systems have enabled remote healthcare and telemedicine. While medical examinations could previously extract only localized symptoms through snapshots, now continuous monitoring can discretely analyze how a patient's lifestyle affects his/her physiological conditions and if additional symptoms occur under various stimuli. We demonstrate how medical applications in particular benefit from a hierarchical networking scheme that will improve the quantity and quality of ubiquitous data collection. Our Telehealth networking infrastructure provides flexibility in terms of functionality and the type of applications that it supports. We specifically present a case study that demonstrates the effectiveness of our networked embedded infrastructure in an in vivo pressure application. Experimental results of the in vivo system demonstrate how it can wirelessly transmit pressure readings measuring from 0 to 1.5 lbf/in (2) with an accuracy of 0.02 lbf/in (2). The challenges in biocompatible packaging, transducer drift, power management, and in vivo signal transmission are also discussed. This research brings researchers a step closer to continuous, real-time systemic monitoring that will allow one to analyze the dynamic human physiology.

The problem of hardware-software codesign for embedded systems using configurable architectures has been studied extensively in the past decade. In this work we studied the feasibility of utilizing Commercial Off-The-Shelf (COTS) FPGA systems for codesign. We partitioned the implementation of a set of benchmark applications on hardware and software and studied the performance and resource consumption in the system. The result of experiments demonstrated that the communication between the processor and the reconfigurable architecture is the major hurdle in the codesign, especially when using COTS System on Chips. It is demonstrated that although implementing algorithms in hardware can lead to enormous speedup, the communication overhead for transferring data variables between the configurable architecture and the processor can destroy all the achieved speedup. We especially showed that in COTS FPGAs this bottleneck is more restricting because of the weak communication structure between different IPs. Furthermore, analyzing the experimental results, we propose a partitioning mechanism; the evaluation results show that the achieved speedup using the proposed partitioning mechanism is between 2 to 300 based on application's data dependency

Several diseases and medical conditions require constant monitoring of physiological signals and vital signs on daily bases, such as diabetics, hypertension and etc. In order to make these patients capable of living their daily life it is necessary to provide a platform and infrastructure that allows the constant collection of physiological data even when the patient is not inside of the coverage area. The data must be rapidly "transported" to care givers or to the designated medical enterprise. The problem is particularly severe in case of emergencies (e.g. natural disasters or hostile attacks) when the communications infrastructure (e.g. cellular telephony, WiFi public access, etc) has failed or is totally congested. In this paper we present an evaluation of of the vehicular ad-hoc networks (VANET) as an alternate method of collecting patient pre-recorded physiological data and at the same time reconfiguring patient medical wearable body vests to select the data specifically requested by the physicians. Another important use of vehicular collection of medical data from body vests is prompted by the need to correlate pedestrian reaction to vehicular traffic hazards such as chemical and noise pollution and traffic congestion. The vehicles collect noise, chemical and traffic samples and can directly correlate with the "stress level" of volunteers.

Remote medical monitoring with medical sensors and wireless communications has recently gained attention for the potential savings and improved quality in patient health-care. Currently, many mobile wireless medical infrastructures connect to the Internet in a point-to-point fashion, such as the cellular network. However, our research investigates new models for remote patient care that exploit P2P networking among patients and healthcare providers (nurses, doctors, emergency personnel). In this paper, we identify several medical applications based on P2P Health Networking focusing on two specific scenarios where nurses and patients are both equipped with Bluetooth devices. Nurses opportunistically collect, share and upload data in a P2P fashion. During an emergency, the nearest nurse is alerted via Bluetooth Enhanced Inquiry Response mechanism. The simulation and test-bed experimentation demonstrate that Bluetooth P2P networking is both feasible and cost-effective in remote medical monitoring.

Power consumption has emerged as the premier and most constraining aspect in modern microprocessor and application-specific designs. Gate sizing has been shown to be one of the most effective methods for power (and area) reduction in CMOS digital circuits. Recently, as the feature size of logic gates (and transistors) is becoming smaller and smaller, the effect of soft-error rates caused by single-event upsets (SEUs) is becoming exponentially greater. As a consequence of technology feature size reduction, the SEU rate for typical microprocessor logic at sea level will go from one in hundred years to one every minute. Unfortunately, the gate sizing requirements of power reduction and resiliency against SEU can be contradictory. 1) We consider the effects of gate sizing on SEU and incorporate the relationship between power reduction and SEU resiliency to develop a new method for power optimization under SEU constraints. 2) Although a nonlinear programming approach is a more obvious solution, we propose a convex programming formulation that can be solved efficiently. 3) Many of the optimal existing techniques for gate sizing deal with an exponential number of paths in the circuit. We prove that it is sufficient to consider a linear number of constraints. 4) We generalize our methodology to include nonlinear delay models and leakage power as well. As an important preprocessing step, we apply statistical modeling and validation techniques to quantify the impact of fault masking on the SEU rate. Furthermore, we adapt our method to incorporate process variation and evaluate our gate sizing technique under uncertainty. We evaluate the effectiveness of our methodology on ISCAS benchmarks and show that error rates can be reduced by a factor of 100%-200% while, on average, the power reduction is simultaneously decreased by less than 6%-10%, respectively, compared to the optimal power saving with no error rate constraints.

In highly power constrained sensor networks, harvesting energy from the environment makes prolonged or even perpetual execution feasible. In such energy harvesting systems, energy sources are characterized as being regenerative. Regenerative energy sources fundamentally change the problem of power scheduling for embedded devices. Instead of the problem being one of maximizing the lifetime of the system given a total amount of energy, as in traditional battery powered devices, the problem becomes one of preventing energy depletion at any given time. Coupling relatively computationally intensive applications, such as video processing applications, with the constrained FPGAs that are feasible on power constrained embedded systems, makes dynamic reconfiguration essential. It provides the speed comparable to a hardware implementation, but it also allows the dynamic reconfiguration to meet the multiple application needs of the system. Different applications can be loaded on the FPGA, as the system's needs change over time. The problem becomes how to schedule the dynamic reconfiguration to appropriately make use of the regenerative energy source, to ensure the proper availability of energy for the system over time. This paper presents a methodology for carrying out dynamic reconfiguration for regenerative energy sources, based on statistical analysis of tasks and supply energy. The approach is evaluated through extensive simulations. Additionally, the implementation has been evaluated on regenerative energy, dynamically reconfigurable prototype, known as the MicrelEye. The approach is shown to miss 57.7% less deadlines on average than the current approach for reconfiguration with regenerative energy sources

Given a set of placed blocks, we present an algorithm that minimally spaces the blocks to ensure routability under several assumptions. By performing a binary search on total width/height of the chip and optimal routing area can be obtained. The proposed technique utilizes a piecewise linear model of the channel width. Based on this model, we introduce LP formulation to determine the optimal channel width considering pin alignment by balancing the wire length and the channel width.

In wireless sensor networks, the data collected from numerous low end sensors can be equivalent or superior to a few high fidelity sensors. In this paper, we evaluate the validity of this concept with low-resolution optical sensors. We implemented passive localization using visual object identification techniques on a field programmable gate array (FPGA) sensor platform. The complexity, memory utilization, and accuracy of our algorithms were analyzed for performance on a resource constrained environment. We show that low-resolution optical sensors can accurately localize objects on a global two dimensional plane. We also present a model that quantifies fidelity versus scale for optical sensors. Using our model and application, we demonstrate that low-fidelity optical sensors are an effective tool in sensor networks and at a certain scale can provide superior coverage of an area over a high-resolution camera. This analysis lays the groundwork for future advances in optical sensors.

Static Single Information (SSI) Form is a compiler intermediate representation that extends the more well-known Static Single Assignment (SSA) Form. In 2005, several research groups independently proved that interference graphs for procedures represented in SSA Form are chordal graphs. This paper performs a similar analysis concerning SSI Form, and proves that interference graphs are interval graphs. The primary consequences of this paper are threefold: (1) Linear scan register allocation for programs in SSI Form can be implemented in such a way that there are no lifetime holes, thereby sidestepping one of the drawbacks that plagued non-SSI implementations; (2) the k-colorable subgraph problem can be solved in polynomial-time for interval graphs, but remains NP-Complete for chordal graphs---to date, no register allocation algorithms have been implemented that solve the k-colorable subgraph problem directly; and (3) liveness analysis converges after a single iteration for programs represented in SSI Form.

High level synthesis transformations play a major part in shaping the properties of the final circuit. However, most optimizations are performed without much knowledge of the final circuit layout. In this paper, we present a physically aware design flow for mapping high level application specifications to a synthesizable register transfer level hardware description. We study the problem of optimizing the data communication of the variables in the application specification. Our algorithm uses floorplan information that guides the optimization. We develop a simple, yet effective, incremental floorplanner to handle the perturbations caused by the data communication optimization. We show that the proposed techniques can reduce the wirelength of the final design, while maintaining a legal floorplan with the same area as the initial floorplan.

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

Light-weight embedded systems are now gaining more popularity due to the recent technological advances in fabrication that have resulted in more powerful tiny processors with greater communication capabilities that pose various scientific challenges for researchers. Perhaps the most significant challenge is the energy consumption concern and reliability, mainly due to the small size of batteries. In this tutorial, we portray a brief description of low-power, light-weight embedded systems, depict several power profiling studies previously conducted, and present several research challenges that require low-power consumption in embedded systems. For each challenge, we highlight how low-power designs may enhance the overall performance of the system. Finally, we present a several techniques that minimize the power consumption in such systems.

In this paper, we develop a mixed-size placement tool, Dragon2006, to solve large scale placement problems effectively. A top-down hierarchical approach based on min-cut partitioning and simulated annealing is used to place very large SoC-style designs containing fixed blockage, movable macro blocks of various sizes and standard cells. Moreover, we have applied several techniques for wirelength optimization, congestion estimation in the presence of blockage and white space allocation for congestion removal.

Register sharing for high-level synthesis of programs represented in static single assignment (SSA) form is proven to have a polynomial-time solution. Register sharing is modeled as a graph-coloring problem. Although graph coloring is NP-Complete in the general case, an interference graph constructed for a program in SSA form probably belongs to the class of chordal graphs that have an optimal O(|V|+|E|) time algorithm. Chordal graph coloring reduces the number of registers allocated to the program by as much as 86% and 64.93% on average compared to linear scan register allocation.

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

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.

Dictionary compression mechanisms identify redundant sequences of instructions that occur in a program. The sequences are extracted and copied to a dictionary. Each sequence is then replaced with a codeword that acts as an index into the dictionary, thereby enabling decompression of the program at runtime. The problem of optimally organizing a dictionary consisting solely of redundant sequences in order to maximize compression has long been known to be NP-Complete [23]. This paper addresses the problem of dictionary construction when redundant code fragments are represented as Data Flow Graphs (DFGs) rather than linear sequences of instructions. Since there are generally multiple legal schedules for a given DFG G, a compiler must determine a schedule for G so that other DFGs that are subgraphs of G can reference some substring of G’s final code sequence. This reduces the size of the dictionary, and in turn, the size of the compressed program. Our experiments with 10 MediaBench [18] applications yielded reductions in dictionary size ranging from 21.14 % to 29.76 % compared to a naïve approach.

We propose a platform for health monitoring using wireless sensor networks. Our platform is a new architecture called CustoMed that will reduce the customization and reconfiguration time for medical systems that use reconfigurable embedded systems. This architecture is a network enabled system that supports various wearable sensors and contains on-board general computing capabilities for executing individually tailored event detection, alerts, and network communication with various medical informatics services. The customization of such system with a large number of "med nodes" is extremely fast even by non-engineering staff. In this paper, we present the architecture of such device along with experimental analysis that evaluates the performance of such system.

This paper presents an efficient technique for placement and routing of sensors/actuators and processing units in a grid network. The driver application that we present is a medical jacket which requires an extremely high level of robustness and fault tolerance. The power consumption of such jacket is another key technological constraint. Our proposed interconnection network is a mesh of wires. A jacket made of fabric and wires would be susceptible to accidental damage via tears. By modeling the tears, we evaluate the probability of having failures on every segment of wires in our mesh interconnection network. Then we study two problems of placement and routing in the sensor networks such that the fault tolerance is maximized while the power consumption is minimized. We develop efficient integer linear programming (ILP) formulations to address these problems and perform both placement and routing simultaneously. This ensures that the solution is a lower bound for both problems. We evaluate the effectiveness of our proposed techniques on a variety of benchmarks.

In this paper, we propose techniques for effective slack management in high-level synthesis. Our design methodology improves the usability of slack. This manifests itself in the form of relaxed latency constraints on resources. Relaxed latency constraints could be exploited to generate designs with better power, area, routability, and other measures. The slack-management engine has two key components: delay budgeting and resource binding. We propose a left edge traversal-based algorithm for delay budgeting. For resource binding, we developed an algorithm that applies a locally optimal binding procedure at each clock step. In order to demonstrate the effectiveness of our strategy, we built an experimental flow that integrated SUIF, Synopsys Design Compiler, Cadence Silicon Ensemble, and our own optimization tools. Experiments with the MediaBench suite shows that our methodology could generate designs with better quality than designs and faster design closure when compared with designs generated without slack management.

Complexities of applications implemented on embedded and programmable systems grow with the advances in capacities and capabilities of these systems. Mapping applications onto them manually is becoming a very tedious task. This draws attention to using high-level synthesis within design flows. Meanwhile, it is essential to provide a flexible formulation of optimization objectives as well as to perform efficient planning for various design objectives early on in the design flow. In this work, we address these issues in the context of data flow graph (DFG) scheduling, which is an essential element within the high-level synthesis flow. We present an algorithm that schedules a chain of operations with data dependencies among consecutive operations at a single step. This local problem is repeated to generate the schedule for the whole DFG. The local problem is formulated as a maximum weight noncrossing bipartite matching. We use a technique from the computational geometry domain to solve the matching problem. This technique provides a theoretical guarantee on the solution quality for scheduling a single chain of operations. Although still being local, this provides a relatively wider perspective on the global scheduling objectives. In our experiments we compared the latencies obtained using our algorithm with the optimal latencies given by the exact solution to the integer linear programming (ILP) formulation of the problem. In 9 out of 14 DFGs tested, our algorithm found the optimal solution, while generating latencies comparable to the optimal solution in the remaining five benchmarks. The formulation of the objective function in our algorithm provides flexibility to incorporate different optimization goals. We present examples of how to exploit the versatility of our algorithm with specific examples of objective functions and experimental results on the ability of our algorithm to capture these objectives efficiently in the final schedules.

Silicon compilers are often used in conjunction with Field Programmable Gate Arrays (FPGAs) to deliver flexibility, fast prototyping, and accelerated time-to-market. Many of these compilers produce hardware that is larger than necessary, as they do not allow instructions to share hardware resources. This study presents an efficient heuristic which transforms a set of custom instructions into a single hardware datapath on which they can execute. Our approach is based on the classic problems of finding the longest common subsequence and substring of two (or more) sequences. This heuristic produces circuits which are as much as 85.33% smaller than those synthesized by integer linear programming (ILP) approaches which do not explore resource sharing. On average, we obtained 55.41% area reduction for pipelined datapaths, and 66.92% area reduction for VLIW datapaths. Our solution is simple and effective, and can easily be integrated into an existing silicon compiler.

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 the past few years, gate duplication has been studied as a strategy for cutset minimization in partitioning problems. This paper addresses the problem of delay optimization by gate duplication. We present an algorithm to solve the gate duplication problem. It traverses the network from primary outputs(PO) to primary inputs(PI) in topologically sorted order evaluating tuples at the input pins of gates. The tuple's first component corresponds to the input pin required time if that gate is not duplicated. The second component corresponds to the input pin required time if that gate were duplicated. After tuple evaluation the algorithm traverses the network from PI to PO in topologically sorted order, deciding the gates to be duplicated. The last and final traversal is again from PO to PI, in which the gates are physically duplicated. Our algorithm uses the dynamic programming structure. We report delay improvements over other optimization methodologies. Gate duplication, along with other optimization strategies, can be used for meeting the stringent delay constraints in today's ultra complex designs.

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.

In this paper, we study the problem of customized regular segmentation design in FPGA routing channels. We propose a deterministic algorithm for segmentation design problem in which each interval is assigned to only one segment (1-Segmentation). We solve the problem of maximum number of incremental track assignment of intervals by mincost network flow technique for 1-Segmentation design. The general K-Segmentation design problem can also be solved by some modifications in our algorithm. We have experimented our algorithm on a set of MCNC benchmarks and compared the routability of the segmented channels with the routability of different segmentations in FPGA routing architectures, one used by industrial Xilinx TM 4000 FPGA series. The experimental results show that the routability of the segmentation in general-purpose architecture can be as low as 18.4% while the routability of our proposed customized segmentation can be as high as 91%. This result shows the gap between the general FPGA routing architecture and customized architecture for a given application can be very significant and our method is capable of generating such optimized segmentation with high routability for a given application.

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.

We propose a new cell moving algorithm to achieve a desired cell density distribution during the detailed placement stage of a large size standard-cell placement flow. To evaluate our algorithm, we also define a distribution deviation metric on how close a placement result is to the target cell density distribution. Experiments show that our approach can generate placement results, which have a cell density distribution closer to the desired distribution with very little increase in the wirelength. We achieve a 32.3% improvement in the distribution deviation at the cost of 11.2% increase in the wirelength on average. Also, the final placement results have 5.9% shorter wirelength than those of an industrial placer, Cadence QPlace.

Programmable logic is emerging as an attractive solution for many digital signal processing applications. In this work, we have investigated issues arising due to the resource constraints of FPGA-based systems. Using an iterative image restoration algorithm as an example we have shown how to manipulate the original algorithm to suit it to an FPGA implementation. Consequences of such manipulations have been estimated, such as loss of quality in the output image. We also present performance results from an actual implementation on a Xilinx FPGA. Our experiments demonstrate that, for different criteria, such as result quality or speed, the best implementation is different as well.

The global routing problem decomposes the large, complex routing problem into a set of more manageable subproblems. The high correlation between the output of the global router and the detailed router enables the designer to efficiently use the global route to refine the design quickly before running the full detailed route. Hence, routability of the global routing solution is the key factor. The routability of the circuit depends on the congestion of the routing. In this paper, we study Steiner trees in terms of routability. We introduce the notion of flexibility, a geometric property associated with Steiner trees. We show that the flexibility of a Steiner tree is related to its routability. The main contribution of this paper is an algorithm which takes a stable Steiner tree as an input and maps it to a more flexible Steiner tree. Any existing Steiner tree algorithm can be used for the initial construction of the Steiner tree. Experiments with a global router on a subset of nets show that routing congestion is improved by approximately 20% locally throughout the region where those nets are routed.

The use of white space in fixed-die standard-cell placement is an effective way to improve routability. In this paper, we present a white space allocation approach that dynamically assigns white space according to the congestion distribution of the placement. In the top-down placement flow, white space is assigned to congested regions using smooth allocating functions. A post-allocation optimization step is taken to further improve placement quality. Experimental results show that the proposed allocation approach, combined with a multilevel placement flow, significantly improves placement routability and layout quality. A set of approaches for white space allocation has been presented and compared in this paper. All of them are based on routability-driven methods. However, these approaches vary in the allocation function and allocation aggressiveness. All the placement results are investigated by feeding them into a widely used industrial router (Warp Route of Cadence). Comparisons have been made between: 1) placement with or without white space allocation; 2) different white space allocation approaches; and 3) our placement flow, industrial placement tool, and the other state-of-the-art academic placement tool.

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.

The increasing demand for complex and specialized embedded hardware must be met by processors which are optimized for performance, yet are also extremely flexible. In our work, we explore the tradeoff between flexibility and performance in the domain of reconfigurable processor design. Specifically, we seek to identify regularly occurring, computation-heavy patterns in an application or set of applications. These patterns become candidates for hard-logic implementation, potentially embedded in the flexible reconfigurable fabric as special optimized instructions. In this work we present an extension to previous work in instruction generation: an algorithm that identifies parallel templates. We discuss the advantages of parallel templates, and prove the correctness of our algorithm. We introduce an All-Pairs Common Slack Graph (APCSG) as an effective tool for parallel template generation. Finally, we demonstrate the effectiveness of our algorithm on several applicationse dataflow graphs, reducing latency on average by 51.98%, without unreasonably increasing chip area.

Optimizing power consumption at high-level is a critical step towards power-efficient digital system designs. This paper addresses the power management problem by scheduling a given control-dominated data flow graph. We discuss delay and power issues with scheduling, and propose an improvement algorithm for insertion of so-called soft edges which enable power optimization under timing constraints. Power savings obtained by our approach on tested circuits range between 15 % and 30 % of the initial power dissipation.

Predictability is the quantified from of accuracy. We propose a predictability driven design methodology. The novelty lies in defining and using the idea of predictability. In order to illustrate the basic concepts we focus on the low power binding problem. The binding problem for low power was solved in [3], [5], but in the presence of in-accuracies, their claims of optimality are imprecise. Our experiments show that these inaccuracies could be as high as 33%. Our methodology could improve this unpredictability to as low as 11% with minimal power penalty (7% on average).

Design hierarchy plays an important role in timing-driven placement for large circuits. In this paper, we present a new methodology for delay budgeting based timing-driven placement. A novel slack assignment approach is described as well as its application on delay budgeting with design hierarchy information. The proposed timing-driven placement flow is implemented into a placement tool named Dragon (timing-driven mode), and evaluated using an industrial place and route flow. Compared to Cadence QPlace, timing-driven Dragon generates placement results with shorter clock cycle and better routability.

In this paper we study the correlation between wirelength and routability for standard-cell placement problem, under the modern place-and-route environment. We present a placement tool named Dragon (version 2.1), and show its ability to produce good quality placement for designs with high row utilization. Compared to an industrial placer and an academic state-of-the-art placer, Dragon can produce placement with better routability and shorter total wirelength. We describe many novel algorithmic details and implementation details of this placement tool. Experimental results show that minimizing wirelength improves routability and layout quality.

This paper presents an activity-sensitive clock tree construction technique for low power design of VLSI clock networks. We introduce the term of node difference based on module activity information, and show its relationship with the power consumption. A binary clock tree is built using the node difference between different modules to optimize the power consumption due to the interconnections (i.e., clock gating signals and clock edges). We also develop a method to determine gating signals with minimum number of transitions. After the clock tree is constructed, the gating signals are optimized for further power savings.

This paper presents effective metrics to evaluate the power dissipation of scheduled data flow graphs (DFGs). This enables early evaluation of schedules without performing the computationally expensive resource-binding step. Our metrics correlate heavily (as high as 0.95 and > 0.75 for most test cases) with power dissipation values obtained after resource binding and rescheduling for power optimization steps. An experimental flow that integrates path-based scheduling, power optimal binding and power driven iterative rescheduling stages is constructed. The flow integrates commercial tools; like Synopsys, VSS and academic compilers like SUIF in a common optimization framework. Experimental results on DFGs from MediaBench suit also demonstrate the fact that metric evaluation is on average 42.6 times faster than performing optimal binding and iterative power improvement. Hence metric based evaluation enables fast design exploration at early stages.

The use of white space in fixed-die standard-cell placement is an effective way to improve routability. In this paper, we present a white space allocation approach that dynamically assigns white space according to the congestion distribution of the placement. In the top-down placement flow, white space is assigned to congested regions using a smooth allocating function. A post allocation optimization step is taken to further improve placement quality. Experimental results show that the proposed allocation approach, combined with a multilevel placement flow, significantly improves placement routability and layout quality.In our experiments, we compared our placement tool with two other fixed-die placers using an industrial place and route flow. Placements created by all three tools have been routed with an industrial router (Warp Route of Cadence). Compared with a leading-edge industrial tool, our placer produces placements with similar or better routability and on average 8.8% shorter routed wirelength. Furthermore, our tool produces placement that runs faster through the Warp Route compared with the industrial tool. Compared with a state-of-the-art academic placement tool (Capo/MetaPlacer), our placer shows ability to produce more routable placements: for 15 out of all 16 benchmarks our placer's outputs are routable while Capo/MetaPlacer only creates 4 routable placements.

Presents a new concept of potential slack to measure so-called potential performance of digital circuits. Potential means how much improvement could be made in the future in terms of timing, area, and power dissipation. Predicting potential performance helps the circuit designers make good design decisions at a specific level of abstraction. The authors describe two algorithms for potential slack: an optimal algorithm and a fast greedy algorithm. The former is based on a maximal-independent set on transitive graphs, while the latter focuses on potential slack estimation in a greedy manner. Applications to gate- and physical-level design problems are provided to show the effectiveness of potential slack in predicting the potential performance of digital circuits.

Deep submicron effects, along with increasing interconnect densities, have increased the complexity of the routing problem. Whereas previously we could focus on minimizing wirelength, we must now consider a variety of objectives during routing. For example, an increased amount of timing restrictions means that we must minimize interconnect delay. But, interconnect delay is no longer simply related to wirelength. Coupling capacitance has become a dominant component of delay due to the shrinking of device sizes. Regardless, the most important objective is producing a routable circuit. Unfortunately, this often conflicts with minimizing interconnect delay as minimum delay routes create congested areas, for which an exact routing cannot be realized without violating design rules. In this work, we use the concept of pattern routing to develop algorithms that guide the router to a solution that minimizes interconnect delay - by considering both coupling and wirelength-without damaging the routability of the circuit. The paper is divided into two parts. The first part demonstrates that pattern routing can be used without affecting the routability of the circuit. We propose two schemes to choose a set of nets to pattern route. Using these schemes, we show that the routability is not hindered. The second part builds on the previous part by presenting a framework for coupling reduction using pattern routing. We develop theory and algorithms relating pattern routing and coupling. Additionally, we give suggestions on how to extend our theory and use our algorithms for both global and detailed routing.

Congestion is one of the fundamental issues in very large scale integration physical design. In this paper, we propose two congestion-estimation approaches for early placement stages. First, we theoretically analyze the peak-congestion value of the design and experimentally validate the estimation approach. Second, we estimate regional congestion at the early stages of top-down placement. This is done by combining the wire-length distribution model and interregion wire estimation. Both approaches are based on the well-known Rent's rule, which is previously used for wirelength estimation. This is the first attempt to predict congestion using Rent's rule. The estimation results are compared with the layout after placement and global routing. Experiments on large industry circuits show that the early congestion estimation based on Rent's rule is a promising approach.

Routing tools consume a significant portion of the total design time. Considering routability at earlier steps of the CAD flow would both yield better quality and faster design process. In this paper we are presenting a routability-driven clustering method for cluster-based FPGAs. Our method packs LUTs into logic clusters while incorporating routability metrics into a cost function. The objective is to minimize this routability cost function . Our cost function is consistently able to indicate improved routability. Our method yields up to 50 % improvement over existing clustering methods in terms of the number of routing tracks required. The average improvement obtained is 16.5 %. Reduction in number of tracks yields reduced routing area.

We propose a timing driven gate duplication algorithm for the technology independent phase. Our algorithm is a generalization of the gate duplication strategy suggested in [1]. Our technique gets a more global view by duplicating multiple gates at a time. We compare the minimum circuit delay obtained by SIS [2] with the delay obtained by using our gate duplication. Results show that up to 11% improvement in delay can be obtained. Our algorithm does not have an adverse effect on the overall synthesis time, indicating that gate duplication is an efficient strategy for timing optimization.

This paper presents the concept of flexibility -- a geometric property associated with Steiner trees. Flexibility is related to the routability of the Steiner tree. We present an optimal algorithm which takes a Steiner tree and outputs a more flexible Steiner tree. Our experiments show that a net with a flexible Steiner tree increases its routability. Experiments with a global router show that congestion is improved by approximately 20\%.

Cost effective systems use specialization to optimize factors such as power consumption, processing throughput, flexibility or combinations thereof. Reconfigurable systems obtain this specialization at rim-time. System reconfiguration has a vertical, a horizontal and a time dimension. We organize this design space as the reconfiguration hierarchy, and discuss the design methods that deal with it. Finally, we survey existing commercial platforms that support reconfiguration and situate them in the reconfiguration jungle.

Article Share on Layout aware retiming Authors: A. Ranjan Monterey Design Systems, Sunnyvale, CA Monterey Design Systems, Sunnyvale, CAView Profile , A. Srivastava Computer Science Department, Univeristy of California, Los Angeles, CA Computer Science Department, Univeristy of California, Los Angeles, CAView Profile , V. Karnam Advanced Micro Devices, Sunnyvale, CA Advanced Micro Devices, Sunnyvale, CAView Profile , M. Sarrafzadeh Computer Science Department, Univeristy of California, Los Angeles, CA Computer Science Department, Univeristy of California, Los Angeles, CAView Profile Authors Info & Claims GLSVLSI '01: Proceedings of the 11th Great Lakes symposium on VLSIMarch 2001 Pages 25–30https://doi.org/10.1145/368122.368153Online:01 March 2001Publication History 6citation186DownloadsMetricsTotal Citations6Total Downloads186Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present an algorithm for simultaneous template generation and matching. The algorithm profiles the graph and iteratively contracts edges to create the templates. The algorithm is general and can be applied to any type of graph, including directed graphs and hypergraphs. We discuss how to target the algorithm towards the novel problem of instruction generation and selection for a hybrid (re)configurable systems. In particular, we target the strategically programmable system, which embeds complex computational units like ALUs, IP blocks, etc. into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. Additionally, instruction generation can be used to create soft macros tightly sequenced pre-specified operations placed in the configurable fabric.

Emerging reconfigurable systems attain high performance with embedded optimized cores. For mapping designs on such special architectures, synthesis tools, that are aware of the special capabilities of the underlying architecture are necessary. We propose an algorithm to perform simultaneous scheduling and binding, targeting embedded reconfigurable systems. The algorithm differs from traditional scheduling methods in its capability of efficiently utilizing embedded blocks within the reconfigurable system. The algorithm can be used to implement several other scheduling techniques, such as ASAP, ALAP, and list scheduling. Hence we refer to it as a super-scheduler. The algorithm is a path-based scheduling algorithm. At each step, an individual path from the input DFG is scheduled. The experiments with several DFGs extracted from MediaBench suite indicate promising results. The scheduler presents the capability to perform the trade-off between maximally utilizing the high-performance embedded blocks and exploiting parallelism in the schedule.

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 conflicts between multiple congested regions, and performs local improvement according to the solution of ILP. Experiments show that the proposed approach can effectively reduce the total overflow of global routing result. The short running time of the algorithm indicates good scalability on large designs.

In this wrok, we develop methods to reduce interconnect delay and noise caused by coupling. First, we explain the Coupling-Free Routing (CFR) problem. CFR takes a set of nets and tries to find a one-bend couple-free routing for a subset of nets. A routed net must not couple with any other routed net. We define coupling as a boolean variable which is true when the coupling of two nets is greater than some threshold. Any pair-wise coupling definition can be used. We argue that this problem is useful in both global and detailed routing

No abstract available.

We will review a few key algorithmic and analysis concepts with application to physical design problems. We argue that design and detailed analysis of algorithms is of fundamental importance in developing better physical design tools and to cope with the complexity of present-day designs.

Congestion is one of the fundamental issues in VLSI physical design. In this paper, we propose two congestion estimation approaches for early placement stages. First, we theoretically analyze the peak congestion value of the design and experimentally validate the estimation approach. Second, we estimate regional congestion in the early top-down placement. This is done by combining the wirelength distribution model and inter-region wire estimation. Both approaches are based on the well known Rent's rule, which is previously used for wirelength estimation. This is the first attempt to predict congestion using Rent's rule. The estimation results are compared with the layout after placement and global routing. Experiments on large industry circuits show that the early congestion estimation based on Rent's rule is a promising approach.

In this paper, we investigate reducing the power consumption of a synchronous digital system by minimizing the total power consumed by the clock signals. We construct activity-driven clock trees wherein sections of the clock tree are turned off by gating the clock signals. Since gating the clock signal implies that additional control signals and gates are needed, there exists a tradeoff between the amount of clock tree gating and the total power consumption of the clock tree. We exploit similarities in the switching activity of the clocked modules to reduce the number of clock gates. Assuming a given switching activity of the modules, we propose three novel activity-driven problems: a clock tree construction problem, a clock gate insertion problem, and a zero-skew clock gate insertion problem. The objective of these problems is to minimize the system's power consumption by constructing an activity-driven clock tree. We propose an approximation algorithm based on recursive matching to solve the clock tree construction problem. We also propose an exact algorithm employing the dynamic programming paradigm to solve the gate insertion problems. Finally, we present experimental results that verify the effectiveness of our approach. This paper is a step in understanding how high-level decisions (e.g., behavioral design) can affect a low-level design (e.g., clock design).

In this paper, we show that both the global and local gate duplication problems for delay optimization are NP-complete under certain delay models.

In this paper, we present an approach for applying two supply voltages to optimize power in CMOS digital circuits under the timing constraints. Given a technology-mapped network, we first analyze the power/delay model and the timing slack distribution in the network. Then a new strategy is developed for timing-constrained optimization issues by making full use of stacks. Based on this strategy, the power reduction is translated into the polynomial-time-solvable maximal-weighted-independent-set problem on transitive graphs. Since different supply voltages used in the circuit lead to totally different power consumption, we propose a fast heuristic approach to predict the optimum dual-supply voltages by looking at the lower bound of power consumption in the given circuit. To deal with the possible power penalty due to the level converters at the interface of different supply voltages, we use a "constrained F-M" algorithm to minimize the number of level converters. We have implemented our approach under an SIS environment. Experiment shows that the resulting lower bound of power is tight for most circuits and that the predicted "optimum" supply voltages are exactly or very close to the best choice of actual ones. The total power saving of up to 26% (average of about 20%) is achieved without degrading the circuit performance, compared to the average power improvement of about 7% by the gate sizing technique based on a standard cell library. Our technique provides the power-delay tradeoff by specifying different timing constraints in circuits for power optimization.

Floorplanning is a crucial phase in VLSI physical design. The subsequent placement and routing of the cells/modules are coupled very closely with the quality of the floorplan. A widely used technique for floorplanning is simulated annealing. It gives very good floorplanning results but has major limitation in terms of run time. For circuit sizes exceeding tens of modules simulated annealing is not practical. Floorplanning forms the core of many synthesis applications. Designers need faster prediction of system metrics to quickly evaluate the effects of design changes. Early prediction of metrics is imperative for estimating timing and routability. In this work we propose a constructive technique for predicting floorplan metrics. We show how to modify the existing top-down partitioning-based floorplanning to obtain a fast and accurate floorplan prediction. The prediction gets better as the number of modules and flexibility in the shapes increase. We also explore applicability of the traditional sizing theorem when combining two modules based on their sizes and interconnecting wirelength. Experimental results show that our prediction algorithm can predict the area/length cost function normally within 5-10% of the results obtained by simulated annealing and is, on average, 1000 times faster.

Abstract ⎯ This paper proposes to use voltage-scaling (VS) and gate-sizing (GS) simultaneously for reducing power consumption without violating the timing constraints. We present algorithms for simultaneous VS and GS based on the Maximum-Weighted-Independent-Set problem. We describe the slack distribution of circuit, completeness of gate library and discreteness of supply voltage, and discuss their effects on power optimization. Experimental results show that the average power reduction ranges from 23.3 % to 56.9 % over all tested circuits. I.

Abstract | The multi-way partition problem is very important in various applications. In this paper, we use analytical and experimental results to study the k-way partition problem. We introduce the concept of embedding graph for the the k-way partition problem. Based on this concept, we explain di erent scenarios of using a bi-partition heuristic to solve the k-way partition problem. If C denote the optimal cut cost for the k-way partition problem and the bi-partition heuristics we use are-approzimation heuristics (dened in Section 2), we prove that the cut cost from the hierarchical approach has an approximate upper bound of C log k while the cut cost from the all-way bipartition, or at approach, has an upper bound of Ck. This is contrary to some claims made in recent literature ( and CAD tools designed based on it). Experimental results strongly support our theoretical analysis. Our results show that for large target graph, the hierarchical approach is about 77 % better than the single-pass all-way bi-partition approach. The all-way bi-partition approach will perform better in a multipass set-up. However, the hierarchical approach is still on average 7:1 % better in quality and 144 times faster than the multi-partition all-way bi-partition approach. The main conclusion of this paper is, contradicted to what has been suggested in literature, hierarchical bipartitioning is a more e ective multi-way partitioning scheme. I.

Abstract| Typical placement objectives in volv e reducing net-cut cost or minimizing wirelength.Congestion minimization is least understood, ho w ev er, it models routability most accurately.In this paper, w estudy the congestion minimization problem during placement.First we pointed out that the bounding box router used in [12] is not an accurate measurement of the congestion in the placement.We use a realistic global router to evaluate congestion in the placement stage.This ensures that the nal placement is truely congestion minimized.We also proposed tw o new post processing algorithms, the ow-based cell-centric algorithm and the net-centric algorithm.While the o w-based cell-centric algorithm can move multiple cells at the same time to minimize the congestion, it suers large consumption of memory.Experimental results show that the net-centric algorithm can eectiv ely identify the congested spots in the placement and reduce the congestion.It can produce on an average 7:7% less congestion than the method proposed in [12].Finally, w euse a nal global router to verify that the placement obtained from our algorithm has 39% less congestion than a wirelength-optimized placement obtained by TimberWolf (commercial version 1.3.1).

Improvements in FPGA technology have resulted in the introduction of reconfigurable computing machines, where the hardware adapts itself to the running application to gain speedup. We present a top-down compilation method, under development, for such systems. We compile a C program into hierarchical VHDL source files, and annotate them with the placement information of the hardware modules to be configured on the FPGA. Static scheduling combined with a fast, two-stage placement core reduces the compilation time of large programs to minutes.

No abstract available.

In many applications such as high-level synthesis (HLS) and logic synthesis and possibly engineering change order (ECO) we would like to get fast and accurate estimations of different performance measures of the chip, namely area, delay and power consumption. These measures cannot be estimated with high accuracy unless a fairly detailed layout of the chip, including the floorplan and routing is available, which in turn are very costly processes in terms of running time. As we have entered the deep sub-micron era, we have to deal with designs which contain million gates and up. Not only we should consider the area occupied by the modules, but we also have to consider the wiring congestion. In this paper we propose a cost function that is, in addition to other parameters, a function of the wiring area. We also propose a method, to avoid running the floorplanning process after every change in the design, by considering the possible changes in advance and generating a floorplan which is tolerant to these modifications, i.e., the changes in the netlist does not dramatically change the performance measures of the chip. Experiments are done in the high-level synthesis domain, but the method can be applied to logic synthesis and ECO as well. We gain speedups of 184% on the average over the traditional estimation methods used in HLS.

This paper proposes the concept of potential slack and shows that it is an effective metric of combinational circuit performance. We provide several methods for estimating potential slack and prove one (a maximal-independent-set based algorithm) in particular which works best. Experiments in gate sizing show that potential slack provides 100% correct prediction for circuit area optimization. We also explore the role of potential slack in timing-driven placement.

Comprehensive study of incremental algorithms and solutions in the context of CAD tool development is an open area of research with a great deal of potential. Incremental algorithms for synthesis and layout are needed when design undergoes local or incremental change. Often these local changes are made to react to local change in the design, correct local errors or to make local improvements in one or more of the design quality metrics. In this paper we outline fundamental problems in incremental logic synthesis and physical design. Preliminary solutions to a subset of these problems are outlined.

Predictable routing is the concept of using prespecified patterns to route a net. By doing this, we allow an more accurate prediction mechanism for metrics such as congestion and wirelength earlier in the design flow. Additionally, we can better plan the routes, insert buffers and perform wire sizing earlier. With comparable routing quality we show that we can predictably route up to 30% of a selected subset of nets. Also, we introduce methods for finding a group of nets which can be predictably routed.

Delay optimization is a fundamental goal in logic synthesis. This paper presents gate duplication as a strategy for performance optimization. Many timing optimization strategies have been proposed over the past few years. In the past few years, the research community has looked at gate duplication extensively as a method of reducing the cut-set of partitions. Strategies of logic duplication for cut-set minimization have been suggested. The strength of gate duplication as a cut-set minimizing strategy has been demonstrated. However applicability of this strategy in reducing the circuit delay has not been studied in detail. In this paper we prove the problem of partitioning a set of fanouts between a gate and it's replica (both gates have the same fanins) such that the required time constraint at the input pin is met, to be NP-Complete. Hence even the local optimization by gate duplication problem (formally defined later) is also NP-Complete. We then present an algorithm for gate duplication which is based on the dynamic programming approach. Since the problem of partitioning a set of fanouts between a node and it's replica is NP-Complete, we use a heuristic for making this decision which is optimal under specific conditions. We report delay improvements as high as 8% over highly optimized results generated by SIS. The rest of this paper is organized as follows. Section 2 deals with the delay model and provides basic definitions. Section 3 reviews the complexity of the global gate duplication problem. Section 4 presents the proof of NP-Completeness for the local gate duplication problem. Section 5 describes a heuristic for gate duplication in detail, followed by results in Section 6. This is followed by some observations and conclusion in Section 7.

In this paper, we develop a new standard cell placement tool, Dragon2000, to solve large scale placement problem effectively. A top-down hierarchical approach is used in Dragon2000. State-of-the-art partitioning tools are tightly integrated with wirelength minimization techniques to achieve superior performance. We argue that net-cut minimization is a good and important shortcut to solve the large scale placement problem. Experimental results show that minimizing net-cut is more important than greedily obtain a wirelength optimal placement at intermediate hierarchical levels. We run Dragon2000 on recently released large benchmark suite ISPD98 as well as MCNC circuits. For circuits which have more than 100 k cells, comparing to iToolsl.4.0, Dragon2000 can produce slightly better placement results (1.4%) while spending much less amount of time (2/spl times/ speedup). This is also the first published placement result on the publicly available large industrial circuits.

We propose fresher looks into already existing hierarchical partitioning based floorplan design methods and their relevance in providing faster alternatives to conventional approaches. We modify the existing partitioning based floor-planner to handle congestion and timing. We also explore the applicability of traditional sizing theorem for combining two modules based on their sizes and interconnecting wirelength. The results show that our floorplanning approach can produce floorplans hundred times faster and at the same time achieving better quality (on average 20% better wirelength, better congestion and better timing optimization) than that of pure simulated annealing based floorplanner.

Incremental modification and optimization in VLSI Computer-Aided Design (CAD) is of fundamental importance.However, it has not been investigated as a discipline.Previous research and development effort is very unfocused and incomplete.Comprehensive study of incremental algorithms and solutions in the context of CAD tool development is an open area of research with a great deal of potential.Full understanding and focused participation in research and development in the area of incremental and dynamic would help us cope with the complexity of present day VLSI systems and facilitates concurrent optimization.In this paper we formulate and survey fundamental problems in incremental physical design.Preliminary solutions to a subset of these problems will be outlined.

As technology advances, more and more issues need to be considered in the placement stage, e.g., wirelength, congestion, timing, coupling. It is very hard to consider all of them together at the same time. Thus it is good if we can optimize one cost function without a ecting others. In this paper, we will study methods to optimize congestion in placement without in icting degradations/violations in other objectives or constraint. We give a mathematical equation to predict the over ow within a region using a normal distribution approximation. According to experiments, this equation does give a good estimation of over ow. We used this equation to nd the smallest regions whichhave enough routing resource to alleviate the congestion and propose the exible expansion scheme in our multi-center congestion reduction (MC 2 R) algorithm. Experimental results show that generally there is a correlation between the amount of reduction in congestion and the amount ofchange made to the placement: the more we change the placement, the more reduction in congestion we will get. However, the exible expansion scheme is very e ective in helping us reduce congestion while make only little change to the placement. Comparing to the full expansion scheme (49 % congestion reduction and 6:5 % change in placement), the exible expansion scheme together with MC 2 R algorithm can reduce congestion by almost the same amount (42%) with much less change made to the placement (1:8%). 1.

The standard cell placement problem has been extensively studied in the past twenty years. Many approaches were proposed and proven effiective in practice. However, successful placement tools need enormous time in the course of development. In this paper we propose a new snap-on placement tool, which is based on multilevel hierarchical placement method. It has great flexibility to combine existing packages and techniques in its top-down framework. In addition, it can be used to build a good placement tool in a short amount of time. Some important issues in multilevel hierarchical placement are discussed here. We investigate the behavior of net-cut and wirelength objectives in global placement problem, propose a + level clustering technique and design a new topdown placement method based on partitioning, annealing and + level technique. We alsowork on the trade-off between solution quality and running time during the hierarchical placement. Experimental results show the strength of proposed placement tool, it produces very good results on all benchmarks and the best known result on the largest MCNC benchmark (avql).

A linear arrangement problem, called the minmax mincut problem, emerging from circuit design is investigated. Its input is a series-parallel directed hypergraph (SPDH), and the output is a linear arrangement (and a layout). The primary objective is to minimize the longest path, and the secondary objective is to minimize the cutwidth. It is shown that cutwidth D, subject to longest path minimization, is affected by two terms: pattern number k and balancing number m. Also, k and m are both lower bounds on the cutwidth. An algorithm, running in linear time, produces layouts with cutwidths $D \leq 2(k+m)$. There exist examples with $k=\Omega (N)$, where N is the number of vertices; however, m is always O(log N). We show that every SPDH, after $local\ logic\ resynthesis$ (specifically, after reordering the serial paths), can be linearly placed with cutwidth D=O(log N). Simultaneously, its dual SPDH can be linearly placed with the same vertex order and with cutwidth D=O(log N). Therefore, after local resynthesis the area can be reduced by a factor of N/log N. Application to gate-matrix layout style is demonstrated.

Computer-aided design (CAD) tools are now making it possible to automate many aspects of the design process. This has mainly been made possible by the use of effective and efficient algorithms and corresponding software structures. The very large scale integration (VLSI) design process is extremely complex, and even after breaking the entire process into several conceptually easier steps, it has been shown that each step is still computationally hard. To researchers, the goal of understanding the fundamental structure of the problem is often as important as producing a solution of immediate applicability. Despite this emphasis, it turns out that results that might first appear to be only of theoretical value are sometimes of profound relevance to practical problems, VLSI CAD is a dynamic area where problem definitions are continually changing due to complexity, technology and design methodology. In this paper, we focus on several of the fundamental CAD abstractions, models, concepts and algorithms that have had a significant impact on this field. This material should be of great value to researchers interested in entering these areas of research, since it will allow them to quickly focus on much of the key material in our field. We emphasize algorithms in the area of test, physical design, logic synthesis, and formal verification. These algorithms are responsible for the effectiveness and efficiency of a variety of CAD tools. Furthermore, a number of these algorithms have found applications in many other domains.

Typical placement objectives involve reducing net-cut cost or minimizing wirelength. Congestion minimization is the least understood, however, it models routability most accurately. In this paper, we study the congestion minimization problem during placement. First, we show that a global placement with minimum wirelength has minimum total congestion. We show that minimizing wirelength may (and in general, will) create locally congested regions. We test seven different congestion minimization objectives. We also propose a post processing stage to minimize congestion. Our main contribution and results can be summarized as follows. (1) Among a variety of cost functions and methods for congestion minimization (including several currently used in industry), wirelength alone followed by a post processing congestion minimization works the best and is one of the fastest. (2) Cost functions such as a hybrid length plus congestion (commonly believed to be very effective) do not always work very well. (3) Net-centric post-processing techniques are among the best congestion alleviation approaches. (4) Congestion at the global placement level, correlates well with congestion of detailed placement.

Advances in programmable hardware have lead to new architectures where the hardware can be dynamically adapted to the application to gain better performance. There are still many challenging problems to be solved before any practical general-purpose reconfigurable system is built. One fundamental issue is the placement of the modules on the reconfigurable functional unit (RFU). In this paper we present an online heuristic placement method with overall O(n log n) space complexity and O(log n) time complexity for each insertion/deletion of modules on the RFU chip, n being the number of modules currently on the RFU. Our proposed method is O(n) faster than an algorithm which considers all possible locations for placing a new module, but as experimental results show its quality is 7% worse.

One of the foremost problems in physical design for deep-submicron circuits is the need for estimates that depend on future decisions. Estimation of area, timing, and coupling are required. We propose a novel floorplanner, with a new wiring metric, which can be updated quickly in small increments. This provides tools with a way to influence the floorplan as they make changes without large running time penalty. We provide experimental results that show the incremental approach to be generally 5 times faster than full floorplanning while maintaining good estimates.

The dual-voltage approach has emerged as an effective and practical technique for power reduction. In this paper, we explore power optimization with dual supply voltages under given timing constraints. By analyzing the relations among the timing slack, delay and power consumption in a given circuit, we relate the voltage-scaling power optimization to the maximal weighted independent set (MWIS) problem, which is polynomial-time solvable on a transitive graph. Then we develop a provably good lower-bound algorithm based on MWIS to generate the lower bound of the power consumption. Also, we propose a fast approach to predict the optimum supply voltages. The maximum power reduction is obtained by using a modified lower-bound algorithm with optimum voltages. Experimental results show that the resulting lower bound is tight for most circuits and that the estimated optimum supply voltage is exactly, or very close to, the best choice of actual voltages.

We present an approach for applying two supply voltages to optimize power in CMOS digital circuits under the timing constraints. Given a technology-mapped network, we first analyze the timing slack distribution and power/delay model within the circuit. The power reduction is then translated into the Maximal-Weighted-Independent-Set (MWIS) problem. We develop an effective power optimization algorithm based on MWIS. To reduce the possible power penalty of level converters (LCs) at the interface of two supply voltages, we use a "constrained" F-M algorithm to minimize the number of LCs. Experimental results show that the total power saving up to 35% (average of about 19%) is achieved without degrading the circuit performance. The power-delay tradeoff is provided by specifying different timing constraints for power optimization.

Typical placement objectives involve reducing net-cut cost or minimizing wirelength.Congestion minimization is least understood, however, it models routability accurately.In thii paper, we study the congestion minimization problem during placement.We introduce the notion of consistent routing model and promote its adoption by placement systems.First, we show that in thii model the wirelength objective is indeed a good measure of congestion by establishing that a placement with minimum wirelength has minimum total congestion.We show that miniibmg wirelength may (and in general, will) create locally congested regions.We demonstrate that most other congestion related objectives are ill behaved and they should only be used in a post processing step.We then propose several novel congestion minimization objectives.One in psrticulsr, called overflow minimization with look-ahead, performs very well and can be computed very efficiently in an incremental manner.At the end, we propose a post processing phase that further improves the congestion.By combining the overflow minimization with look-ahead and the post processing phase, we improve the congestion by more than 40% on the average.

Floorplanning is an early phase in chip planning. It provides information on approximate area, delay, power, and other performance measures. Careful floorplanning is, thus, of extreme importance. In many applications, while a good floorplan is needed, the information about all modules is not available, or even worse, part of the provided information is inaccurate. Examples of such applications are designing a huge system where the floorplan is needed early in the design process, but not all the modules have been designed. Another example is the field of reconfigurable computing where it is not known what modules will be needed on the reconfigurable chip as the program is being executed. Floorplanning with uncertainty is the problem of obtaining a good floorplan when the information about module dimensions is not complete. In this paper, the floorplanning problem with uncertainty is formulated. Correlation between input characteristics and output characteristics is studied. Also, it is established that traditional floorplanners are incapable of efficiently handling uncertainty. An effective method for dealing with uncertain data is proposed. Experiments show that, for example, with up to 30% input uncertainty an area estimate with less than 7% error can be obtained.

Logic partitioning is an important area of very large scale integration computer aided design and there have been numerous approaches proposed. Logic replication, the duplication of logic in order to minimize communication between partitions, can be an effective component of a complete partitioning solution. In this paper we seek a better understanding of the important issues in logic replication. By adding new optimizations to existing algorithms we are able to significantly improve the quality of these techniques, achieving up to 13.9% better results than the best existing replication techniques. When integrated into our already state-of-the-art (nonreplication) partitioner, we improve overall cutsizes by 38.8%, while requiring the duplication of at most 7% of the logic.

Traditional placement problems are studied under a fully specified cell library and a complete netlist. However, in the first, e.g., 2 years of a 2-3 year microprocessor design cycle, the detailed netlist is unavailable. For area and performance estimation, layout must nevertheless be done with incomplete information. Another source of incompleteness comes from reuse of instances from earlier design generations; these instances and their parameters will change as the project evolves. The problem of placement with incomplete data (PID) can be abstracted as having to place a circuit when p/sub c/% of the cells and p/sub n/% of the nets are missing. The key challenge in PID is how to add missing cells and nets. In this paper, two patching-methods for adding missing nets and cells are proposed. The methods are called abstraction and fusion. Experimental results are very interesting and illustrative. First, they show that PID is a difficult problem and an arbitrary (and perhaps intuitively sound) method may not produce high-quality results. Experiments verify that the abstraction method is a very good predictor and that fusion is not because circuits produced by abstraction attain much of the properties of the original circuits. Summary Table 3 in Section 4 shows that when a circuit has 10% incompleteness, abstraction can predict the final total wirelength with an error of 5.8%, while fusion has a 67.8% error in predicting the wirelength in the same circuit.

We investigate the problem of exploiting signal correlation between operations to find a schedule and binding which minimizes switching. We propose several heuristics to solve the problem. Experimentally, we give an algorithm for scheduling communications on a bus, which reduces bus switching up to 60%, without increasing the number of cycles required for the schedule. Low-power scheduling efforts in the literature have focused on decreasing the number of cycles in the schedule so that the voltage required to run the resulting circuit can be lowered. However, the number of voltages supplied to a chip is likely to be limited, so among the processes to be implemented, typically only a few will determine the minimum voltages, and the rest will have slack in their schedules. Therefore it is interesting to inquire about the impact of scheduling which does not reduce the number of time steps in order to decrease switching. In this paper, we show that power-aware scheduling can lead to significant decreases in switching, often without an increase in the number of time steps required. The technique is general, and can be used to schedule operations on any kind of resources.

Floorplanning is an early phase in chip planning. It provides information on approximate area, delay, power, and other performance measures. Careful floorplanning is thus of extreme importance. In many applications while a good floorplan is needed, not all modules' information are available, or even w orse, part of the pro vided information is inaccurate. Floorplanning with uncertainty is the problem of obtaining a good floorplan under uncertainty. In this paper, the floorplanning problem with uncertainty is form ulated. It is established that traditional floorplanners are incapable of handling uncertainty. An effective method for dealing with uncertain data is proposed. Experiments sho w that, for example, with up to 30% input uncertainty an area estimate with less than 7% error can be obtained.

There are a number of VLSI problems that have a common structure. We investigate such a structure that leads to a unified approach for three independent VLSI layout problems: partitioning, placement, and via minimization. Along the line, we first propose a linear-time approximation algorithm on maxcut and two closely related problems: k-coloring and maximal k-color ordering problem. The k-coloring is a generalization of the maxcut and the maximal k-color ordering is a generalization of the k-coloring. For a graph G with e edges and n vertices, our maxcut approximation algorithm runs in O(e+n) sequential time yielding a nodebalanced maxcut with size at least (w(E)+w(E)/n)/2, improving the time complexity of O(e log e) known before. Building on the proposed maxcut technique and employing a height-balanced binary decomposition, we devise an O((e+n)log k) time algorithm for the k-coloring problem which always finds a k-partition of vertices such that the number of bad (or "defected") edges does not exceed (w(E)/k)((n-1)/n)/sup log k/, thus improving both the time complexity O(enk) and the bound e/k known before. The other related problem is the maximal k-color ordering problem that has been an open problem. We show the problem is NP-complete, then present an approximation algorithm building on our k-coloring structure. A performance bound on maximal k-color ordering cost, 2kw(E)/3 is attained in O(ek) time. The solution quality of this algorithm is also tested experimentally and found to be effective.

We study the reproducing placement problem, which finds application in layout-driven logic synthesis. In each phase, a module (or gate) is decomposed into two (or more) simpler modules. The goal is to find a "good" placement in each phase. The problem, being iterative in nature, requires an iterative algorithm. In solving the RPP, we introduce the notion of minimum floating Steiner trees (MFST). We employ an MFST algorithm as a central step in solving the RPP. A Hanan-like theorem is established for the MFST problem, and two approximation algorithms are proposed. Experiments on commonly employed benchmarks verify the effectiveness of the proposed technique.

We propose a new global net distribution approach for high-performance m/spl times/m two-dimensional arrays of very large scale integration and multichip-modules. The objective is to route n nets with minimum density of global cells, using a "small" number of bends. There are a number of applications where it is necessary to limit the number of bends on each wire. For example, it is desirable to limit the number of bends on each microstrip (transmission) line, for mismatches of line impedance can cause reflections from the junction points such as bends and vias. Furthermore, for high-performance routing, intersections of wires cause the use of more vias, which in turn require the use of more routing resources (because of the larger via pitch). This is the first paper that addresses a graph-theoretic framework to solve the bend-constrained global routing problem in two-dimensional arrays. In this paper, at each level of an underlying quad-tree, we present a novel four-bend routing algorithm by decomposing the original problem at level i into two subproblems that can be solved exactly based on a two-stage approach of smaller-sized linear program followed by min-cost flow networks. The overall (i.e., entire level of the four-way partition hierarchy) constraint and variable size for the first stage is O(md/sub o/), while the overall run time for the second stage is O(n/sup 3/ log n/sup 2/). The time complexity of such a hierarchical approach is one order of magnitude less than one of constructing a global routing using the min-cost-flow-based flat design approach. Last, we present an extension that permits a limited degree of control over the number of bends. The proposed algorithm can also be used for estimating the wireability in the early design planning stage for high-level synthesis. Experimental results showed the effectiveness of the proposed algorithm.

We consider the problem of minimizing power consumption of a sequential circuit using low power state encoding. One of the previously published results is based on recursive matching. In general, a matched pair can be considered as a 1-cube being embedded in a hypercube. We generalize this idea of 1-cube embedding and propose a new encoding algorithm based on r-cube embedding. We then present an efficient 2-cube embedding based state encoding approach for low power design. It considers both Hamming distance and the complexity of the logic function (by estimation). Experimental results show that this approach is competitive to other existing techniques.

In this paper we present a novel formulation for the net-based timing-driven placement problem. The new formulation performs budgeting #net delay upper bounds# and placement modi#cation simultaneously thus alleviates the problem of going back-and-forth between budgeting and placement. An algorithm to accomplished the proposed task is presented. The proposed algorithm uses a simulated annealing approach and a modi#ed graph-based simplex method. A general formulation of timing-sriven placement is presented. It is proved that both net-based and path-based approaches to timing-driven placement are special cases of a more general formulation. The proposed algorithm has been incorporated into a #timing-driven# placement package. Experiments on MCNC benchmarks show strong results. The proposed algorithm o#ers 54# to 68# reduction over the longest path compared with the existing algorithms. 1. INTRODUCTION Timing-driven placement is a problem that is becoming increasingly important in VLSI d...

Logic replication, the duplication of logic in order to limit communication between partitions, is an effective part of a complete partitioning solution. In this paper we seek a better understanding of the important issues in logic replication. By developing new optimizations to existing algorithms we are able to significantly improve the quality of these techniques, achieving up to 12.5% better results than the best existing replication techniques. When integrated into our already state-of-the-art partitioner we improve overall cutsizes by 37.8%, while requiring the duplication of at most 7% of the logic.

We present a new approach to the placement problem. The proposed approach consists of analyzing the input circuit and deciding on a two-dimensional global grid for that particular input. After determination of the grid size, the placement is carried out in three steps: global placement, detailed placement, and final optimization. We show that the output of the global placement can also serve as a fast and accurate predictor. Current implementation is based on simulated annealing. We have put all algorithms together in a placement package called NRG (pronounced N-er-G). In addition to area minimization, NRG can perform timing-driven placement. Experimental results are strong. We improve TimberWolf's results (version 1.2) by about 5%. Our predictor can estimate the wavelength within 10-20% accuracy offering 2-20x speedup compared with the actual placement algorithm.

In this paper, we present a new, general approach to the problem of computing upper bounds on net delays. The upper bounds on net delays are computed so that timing constraints between input and output signals are satisfied. The set of delay upper bounds is called a delay budget. The objective of this work is to compute a delay budget that will lead to timing feasible circuit placement and routing. In our formulation, we find a delay budget so that the placement phase has "maximum flexibility." We formulate this problem as a convex programming problem and prove that it has a special structure. We utilize the special structure of the problem to propose an efficient graph-based algorithm. We present experimental results for our algorithms with the MCNC placement benchmarks. Our experiments use budgeting results as net length constraints for the TimberWolf placement program, which we use to evaluate the budgeting algorithms. We obtain an average of 50% reduction in net length constraint violations over the well-known zero-slack algorithm (ZSA). We also study different delay budgeting objective functions, which yield 2/spl times/ performance improvements without loss of solution quality. Our results and graph-based formulation show that our proposed algorithm is suitable for modern large-scale budgeting problems.

In this paper, we investigate the problem of computing a lower bound on the number of buffers required when given a maximum clock slew rate (or rise time) constraint and a predefined clock tree. Using generalized properties of published CMOS timing models, we formulate a novel nonlinear buffer insertion problem. Next, we derive an algorithm that bounds the capacitance for each buffer stage without sacrificing the generality of the timing models. With this capacitance bound we formulate a second linear buffer insertion problem, which we solve optimally in O(n) time. The basic formulation and algorithm are extended to include a skew upper bound constraint. Using these algorithms we propose further algorithmic extensions that allow area and phase delay tradeoffs. Our results are verified using SPICE3e2 simulations with MCNC MOSIS 2.0 /spl mu/ models and parameters. Experiments with these test cases show that the buffer insertion algorithms proposed herein can be used effectively for designs with high clock speeds and small skews.

In this paper we examine the problem of reducing the power consumption of a technology mapped circuit under timing constraints. Consider a cell library that contains multiple implementations (cells) of the same Boolean function. We first present an exact algorithm for the problem when a complete library is given in a complete library, all implementations of each cell are present. We then propose an efficient algorithm for the problem if the provided library is not complete.

Sleep mode operation and exploiting it to minimize the average power consumption are o f g r e at importance.In this paper, we formulate the memory segmentation/partitioning problem to exploit sleep mode operation and show that the problem is NP-complete.We present polynomial time algorithms for special classes of the problem.Some generalizations of the problem are discussed.Preliminary experiments are c onducted to show the eectiveness of the algorithms and applicability of the approach.The experimental data con rm that a careful partitioning allows up to 40% more sleep time which could be exploited to minimize the average power consumption.Directions for further research in this area a r e presented.

Partitioned memory with bus interconnect architecture in its most general form consists of several functional units with associated memory accessible to the functional unit via local interconnect and global buses to communicate data values across from one functional unit to another.As can be expected, the time at which certain values are c ommunicated aect the size of the local memories and the number of buses that are n e e ded.We address the problem of scheduling communications in a bus architecture under memory constraints.We present here a network ow formulation for the problem and obtain an exact algorithm to schedule the communications, such that the constraint on the number of registers in each functional unit is satis ed.As an increasing number of architectures use multiple memories in addition to (or instead of) one central RAM, this work is especially interesting.Several authors have already studied this problem in related a r chitectures, yet all use heuristic approaches to schedule the communications.Our technique is the rst exact solution to the problem.Also, our graph theoretic formulation provides a clearer insight into the problem.

Partitioning of a system to maximize exploitable sleep time for low-power synthesis is discussed. The motivation is to deactivate the memory refresh circuitry, apply power down or disable the clock signals during the inactive periods of operation of circuit elements, and thus minimize the power consumption. Since it is impractical to have a separate set of control signals for each circuit element (otherwise, the control itself would consume a lot of power), it is advisable to partition a circuit based on the activity patterns of its elements so that the partitions can be switched into sleep mode for long periods of time. In this paper, we formulate this partitioning problem and show that it is NP-hard. We present Geo-Part, a geometric partitioning heuristic for this problem. An efficient implementation of Geo-Part using segment tree data structure is discussed. Experimental results are encouraging.

In this paper we investigate activity-driven clock trees to reduce the dynamic power consumption of synchronous digital CMOS circuits. Sections of an activity-driven clock tree can be turned on/off by gating the clock signals during the active/idle times of the clocked elements. We propose a method of obtaining the switching activity patterns of the clocked circuits during the high level design process. We formulate three novel activity-driven problems. The objective of these problems is to minimize system's dynamic power consumption. We propose an approximation algorithm based on recursive matching to solve the clock tree construction problem. We solve the gate insertion problems with an exact algorithm employing the dynamic programming paradigm. Finally, we present experimental results that verify the effectiveness of our approach. Our work in this paper is a step in understanding how high level decisions (e.g. behavioral design) can affect a low level design (e.g. clock design).

We address the problem of state encoding for synchronous finite state machines (FSM's), targeted for low power design. Most previous work in FSM state encoding has been focused on minimizing chip area and does not consider switching activity of the circuit. As a result, this does not always lead to a power efficient implementation. Especially in CMOS circuits, the switching activity is a very important factor in power dissipation. In this work, we define a function /spl lambda/ for automatic tradeoff between switching activity and area that contribute to power dissipation. /spl lambda/ is used in determining the encoding affinity between states and is observed to be related to the number of states of a FSM in our experiments. A state encoding algorithm, based on hypercube embedding, is proposed to find encodings of states such that the sum of bit toggles between each pair of states times the encoding affinity between them is minimized. Results over a wide range of MCNC benchmark examples which show the efficacy of our technique are presented.

A linear arrangement problem, called the minmax mincut problem, emerging from circuit design is investigated. Its input is a series-parallel directed hypergraph, and the output is a linear arrangement (and a layout). The primary objective is to minimize the longest path, and the secondary objective is to minimize the cutwidth. It is shown that cutwidth D, subject to longest path minimization, is affected by pattern number k, which is also a lower bound on the cutwidth but not a tight one. There exist examples with k=/spl Omega/(N), where N is the number of vertices. We propose an algorithm producing cutwidths D=O(k+log N). We also show that every series-parallel directed hypergraph, after reordering the serial paths, can be linearly placed with cutwidth D=O(log N). Simultaneously, its dual series-parallel directed hypergraph can be linearly placed with the same vertex order and with cutwidth D=O(log N). Applications on gate-matrix layout style in very large-scale-integrated (VLSI) CMOS circuit design are demonstrated.

Given a set of terminals on the plane N=(s,/spl nu//sub 1/,...,/spl nu//sub n/,), with a sink terminal s, a Rectilinear Distance-Preserving Tree (RDPT) T(V, E) is defined as a tree rooted at s, connecting all terminals in N. The rectilinear distance between source and sinks in an RDPT is equal to the length that source to sink path. A Min-Cost Rectilinear Distance Preserving Tree (MRDPT) is an RDPT T* such that all other RDPTs T' connecting s and N have C(T*)/spl les/C(T'), where C(T) denotes the total length of tree T. MRDPTs minimize the total wire length while maintaining minimal source to sink linear delay, making them suitable for high performance interconnect applications. In this paper we investigate exact algorithms for restricted versions of the problem. These algorithms have O(n/sup 2/) time complexity. We propose a heuristic algorithm for the general problem where we partition the points into sets of points that we can solve optimally. The results of our algorithms are tested on random point sets and compared our results are compared with Minimum Cost Steiner tree approximations, showing total wire-length comparisons. The results of these comparisons show that the algorithms proposed herein produce promising results.

Previous algorithms on rectangular dual graph floorplanning generate general floor-plans which include the class of nonsliceable floorplans. We examine the framework of generating sliceable floorplans using the rectangular dual graph approach and present an algorithm that generates a sliceable floorplan if the input graph satisfies certain sufficient conditions. For general input, the algorithm is still able to generate sliceable floorplans by introducing pseudomodules where the areas occupied by the pseudomodules are used for wiring. For an n-vertex adjacency graph, the algorithm generates a sliceable floorplan in $O( n\log n + hn )$ time where h is the height of the sliceable floorplan tree.

In this paper we study the problem of "properly" distributing the set of crossings (i.e., intersection of nets), of a given global routing, among the regions. Each region is assigned a quota, being the maximum number of crossings allowed in that region, which depends on its area and its complexity (e.g., the number of wets going through it and the number of terminals it contains). The crossing distribution problem (CDP) is to find a net ordering at each boundary as to minimize the total number of crossings and to satisfy the quotas. We propose an O(mn/sup 2/+m/spl xi//sup 3/2/) time algorithm for CDP, where m is the number of modules, n is the number of nets, and /spl xi/ is the number of crossings.>

We propose a new approach for optimizing clock trees, especially for high-speed circuits. Our approach provides a useful guideline to a designer, by user-specified parameters, and three of these tradeoffs are provided in this paper. (1) First, to provide a "good" tradeoff between skew and wire length, a new clock tree routing scheme is proposed. The technique is based on a combination of hierarchical bottom-up geometric matching and minimum rectilinear Steiner tree. Our experiments complement the theoretical results. (2) For high-speed clock distribution in the transmission line mode (e.g., multichip modules) where interconnection delay dominates the clock delay, buffer congestion might exist in a layout. Using many buffers in a small wiring area results in substantial interline crosstalks as well as wirability, when the elongation of the imbalanced subtrees is necessary. Placing buffers evenly (locally or globally) over the plane at the minimum impact on wire length increase helps avoid buffer congestion and results in less crosstalk between clock wires. Thus, an effective technique for buffer distribution is proposed. Experimental results verify the effectiveness of the proposed algorithms. (3) Finally, a postprocessing step constraining on phase-delay is also proposed. The technique is based on a combination of hierarchical bottom-up geometric matching and bounded radius minimum spanning tree. The proposed algorithm has an important application in MCM clock net synthesis as well as VLSI clock net synthesis.>

Presents a global approach to solve the three-layer wirability problem for knock-knee layouts. In general, the problem is NP-complete. Only for very restricted classes of layouts polynomial three-layer wiring algorithms are known up to now. The authors show that for a large class of layouts a three-layer wiring can be constructed by solving a path problem in a special class of graphs or a two-satisfiability problem, and thus may be wired in time linear in the size of the layout area. Moreover, it is shown that a minimum stretching of the layout into a layout belonging to this class can be found by solving a clique cover problem in an interval graph. This problem is solvable in time linear in the size of the layout area as well. Altogether, the method also yields a good heuristic for the three-layer wirability problem for knock-knee layouts.>

We consider the problem of global routing, aiming to simultaneously minimize wire length and density through the regions. Previous global routers have attempted to achieve this goal; however, they minimized one of the two parameters as the main objective and proposed heuristics for minimizing the other parameter. We accomplish this task by introducing the concept of weighted Steiner trees. We propose an efficient and simple algorithm for obtaining a weighted (rectilinear) Steiner tree in the plane. The proposed global router at each step finds a weighted Steiner tree for a net, where weight of a region represents its "complexity". Weights of the regions are dynamically changing. Experimental results on master slice chips and on benchmark examples from the Physical Design Workshop are included, and they verify the effectiveness of the proposed global router and its superiority over related global routers.>

One of the main objectives in the process of mapping a digital circuit onto a LUT-based FPGA structure is minimizing the total number of lookup tables needed to implement the circuit. This will increase the size of the circuit that can be implemented using the available FPGA structure. In this paper, we show that even restricted cases of the lookup-table minimization for FPGA technology mapping are NP-complete (even when K is a small constant), and that it can be solved optimally for all values of K on a tree input in O(min{nK, nlogn}) time where n is the number of nodes in the network and K is the input capacity of the LUT's. Based on our algorithm for trees, we present a polynomial time heuristic algorithm for general Boolean networks. Experimental results confirm substantial decrease on the number of LUT's on a number of MCNC logic synthesis benchmarks compared to the algorithms that allow no or just local exploitation of Boolean properties of the circuit. We obtain 10% to 80% improvement on the number of LUT's compared to the previous algorithms (even though we allow very limited operations, e.g., we do not exploit Boolean properties of the circuits or decompose nodes).>

In boundary single-layer routing with slidable or permutable terminals (BSLR-S or BSLR-P), the assumption that each net may have more than one terminal in a range or cluster should be removed. An example that shows Pick-Closest might report "unsolvable" for a solvable instance is considered. It is clear that the instance is solvable if (and only if) the two terminals of net N/sub 1/ are assigned to vertices c and d. However, Pick-Closest will assign the two terminals of net N/sub 1/ to vertices /spl lcub/b,c/spl rcub/ or /spl lcub/d,e/spl rcub/, then report "unsolvable" due to the failure in routing net N/sub 2/. Thus, Pick-Closest only works in instances when each net has at most one terminal in a range. Since BSLR-P also includes slidable terminals, we employ Pick-Closest to solve BSLR-P when TR-permutation is determined by Greedy-Assignment. Thus in BSLR-P, each net can have at most one terminal in a cluster as well. The time complexity of the problem of boundary single-layer routing with slidable and permutable terminals remains open if a net is allowed to have multiple terminals in a cluster.>

We introduce the single-layer global routing problem (SLGRP), also called homotopic routing or rubber-band-equivalent routing, and propose a technique for solving it. Given a set of nets, the proposed technique first determines the routing sequence based on the estimated congestion, the bounding-box length and priority. Then, it finds a routing path, being a sequence of tiles, for each net (one net at a time), avoiding "congested" areas. The overall goal of the algorithm is to maximize the number of routed nets. The proposed global router is the first true single-layer global router ever reported in the literature. The size of tiles, w/spl times/w, is an input parameter in our algorithm. For w=1, the proposed global router serves as an effective detailed router. An optimal postprocessing algorithm, minimizing wire length and number of bends, under homotopic transformation, is presented. The technique has been implemented and tried out for randomly generated data. The algorithm is very efficient and produces good results.>

Article A buffer distribution algorithm for high-speed clock routing Share on Authors: Jun Dong Cho View Profile , Majid Sarrafzadeh View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 537–543https://doi.org/10.1145/157485.165019Published:01 July 1993 18citation291DownloadsMetricsTotal Citations18Total Downloads291Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Sliceable floorplans attain nice properties. In particular, a number of NP-hard problems can be solved efficiently on sliceable floorplans. Most floorplanning algorithms/packages do not produce sliceable floorplans; besides, there are adjacency requirements that are inherently non-sliceable. Motivated by that, we propose a polynomial-time algorithm for transforming an arbitrary floorplan into a sliceable one. We operate on a given sized floorplan to transform it into a sliceable one. Experimental results show that on industrial benchmarks the area increase, enforcing sliceability, is 6% on the average. The percentage of changes in the input adjacency graph (i.e., number of edge detention-addition divided by the total number of edges) is 7% on the average. The proposed algorithm can serve as a post-processor for other floor-planning algorithms. The proposed technique also provides new insights into the class of sliceable floorplans.

Given a two-dimensional point set $\rho $, a chain C is a subset of $\rho $ in which for every two points one is dominated by the other. A k-chain is a subset of $\rho $ that can be partitioned into k-chains. The size of a k-chain is the total number of its points. A k-chain with maximum size, among all possible k-chains, is called a maximumk-chain. First geometric properties of k-chains are studied for an arbitrary k. Then a $\Theta (n\log n)$-time algorithm is presented for finding a maximum three-chain in a point set $\rho $, where $n = |\rho |$.

Given a planar triangulated graph (PTG) G, the problem of constructing a floor-plan F such that G is the dual of F and the boundary of F is rectangular is studied. It is shown that if only zero-concave rectilinear modules (CRM) (or rectangular modules) and 1-CRM (i.e., L-shaped) are allowed, there are PTGs that do not admit any floor-plan. However, if 2-bend modules (e.g., T-shaped and Z-shaped) are also allowed, then every biconnected PTG admits a floor-plan. Thus, the employment of 2-bend modules is necessary and sufficient for graph dualization floor-planning. A linear-time algorithm for constructing a 2-CRM floor-plan of an arbitrary PTG is proposed.

An arbitrary single-layer detailed routine L of a set of two-terminal nets is considered. The necessary and sufficient condition for a layout to have minimum length under homotopic transformations (i.e. without changing the given global routing) is presented. Based on the proposed classification and the motion of line-segment visibility, an exact algorithm that minimizes the total wire length of L is given. The proposed algorithm runs in O(n/sup 2/) time, where n is the number of bends in L.>

The WISER algorithm for over-the-cell channel routing in the standard cell design style using the two-layer routing model is presented. The novelty of this approach lies in the use of vacant terminals for over-the-cell routing. Longest paths in the vertical constraint graph and channel density are considered as a basis for choosing nets to route over the rows of standard cells. WISER has been implemented and tested on several benchmarks, including PRIMARY1 and Deutsch's difficult example. The experimental results show that WISER reduces the channel height by an average of 29%, as compared to conventional channel routers, and 15%, as compared to existing over-the-cell routers. In addition, it reduces the total number of vias per routing by 32%.>

Given a sliceable floorplan and cell sizes, Otten and Stockmeyer (1983) presented an algorithm to find an optimal implementation for each cell. The authors consider a generalized optimal sizing problem on a set of slicing trees related to an adjacency graph. For computation efficiency, they combine the tree enumeration and sizing procedures in a unified algorithm where floorplan trees and sizes are computed simultaneously. The tree enumeration is based on adjacency graph of the input cells, which ensures that the adjacency requirements of the cells are preserved. Time complexity of the algorithm is analyzed and experimental results using MCNC benchmarks are reported.>

The authors consider a Steiner tree S interconnecting a set N of terminals. The minimizing length of S can be shown to be equivalent to the traditional (NP-hard) Steiner tree problem. An exact polynomial-time algorithm for minimizing the length of S when operations on S are limited is presented. These operations are called topology preserving transformations (TPTs). Based on the notion of TPT, an exact algorithm for minimizing the total length of a single-layer layout involving a set of multi-terminal nets and a collection of obstacles is proposed. The algorithm has been used to find a minimum length single-layer layout. The algorithm was also applied to find a Steiner tree interconnecting a net N of terminals. The idea is to find a minimum spanning tree T of N. Then, generate K Steiner trees by randomly flipping edges of T to both its upper- and lower-L-shaped configurations. Then, a topology preserving transformation is applied to each Steiner tree. The best of them is selected as the final Steiner tree. On the average, 9.4% improvement over the MST length has been reported.>

Given a point set $\rho $, a chain is a subset $\mathcal{C} \subseteq \rho $ of points in which, for any two points, one is dominated by the other. A two-chain is a subset of $\rho $ that can be partitioned into two chains. A two-chain with maximum cardinality among all possible two-chains is called a maximum two-chain. This paper presents a $\Theta ( n \log n )$ time and $\Theta ( n )$ space algorithm for finding a maximum two-chain in a point set $\rho $, where $n = | \rho |$. Maximum two-chain has applications in, for example, graph-theoretic problems, VLSI layout, and sequence manipulation.

A Steiner tree with maximum-weight edge minimized is called a bottleneck Steiner tree (BST). The authors propose a Theta ( mod rho mod log mod rho mod ) time algorithm for constructing a BST on a point set rho , with points labeled as Steiner or demand; a lower bound, in the linear decision tree model, is also established. It is shown that if it is desired to minimize further the number of used Steiner points, then the problem becomes NP-complete. It is shown that when locations of Steiner points are not fixed the problem remains NP-complete; however, if the topology of the final tree is given, then the problem can be solved in Theta ( mod rho mod log mod rho mod ) time. The BST problem can be used, for example, in VLSI layout, communication network design, and (facility) location problems.>

The authors propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius minimum routing tree formulation. The authors first present several heuristics with good performance, based on an analog of Prim's minimum spanning tree construction. Next, they give an algorithm which simultaneously minimizes both routing cost and the longest interconnection path, so that both are bounded by small constant factors away from optimal. They also show that geometry helps in routing: in the Manhattan plane, the total wire length for Steiner routing improves to 3/2*(1+(1/ epsilon )) times the optimal Steiner tree cost, while in the Euclidean plane, the total cost is further reduced to (2/ square root 3)*(1+(1/ epsilon )) times optimal. The method generalizes to the case where varying wire length bounds are prescribed for different source-sink paths. Extensive simulations confirm that this approach works well.>

A hierarchical approach to Steiner tree construction in lambda -geometry is proposed. The algorithm runs in time O(n log n) and the length of the constructed tree is at most ( sigma /cos( pi /2 lambda )) times (for lambda =2, 3/2 times) the length of the optimal Steiner tree where n is the cardinality of the point set and it was recently proved that sigma is (2/ square root 3). How to trade off between the running time of the algorithm and the length of the produced Steiner tree is shown. Given enough time, an optimal Steiner tree will be obtained. The algorithm is extended to construct a Steiner tree of a set of subtrees (i.e., partial trees) and runs in O( lambda N log N) time, where N is the total number of edges of the subtrees.>

In this paper, we present a new algorithm, called WISER, for over-the-cell channel routing in the standard cell design technology using the two-layer routing model. The novelty of our approach lies in use of “vacant” terminals for over-the-cell routing. Furthermore, we consider longest paths in the vertical constraint graph as well as channel density as a basis for choosing nets to route over the rows of standard cells. Our approximation algorithm for net selection produces provably good results. Algorithm WISER has been tested on several benchmark examples, and experimental results show that WISER reduces the channel height by an average of 29% as compared to conventional channel routers. In addition, it reduces the total number of vias by 32% in the average case.

The authors present a novel algorithm for three-layer, over-the-cell channel routing of standard cell designs. The novelty of the proposed approach lies in the use of 'vacant' terminals for over-the-cell routing. Furthermore, the authors consider both the maximum cliques in the horizontal constraint graph and the longest paths in the vertical constraint graph as a basis for choosing the nets to route over the cells. They prove that their net selection algorithm is guaranteed to produce a solution within 68% of the optimum. The proposed algorithm has been implemented and tested on several benchmark examples. For the entire PRIMARY 1 benchmark, they reduce the total routing height by 76% as compared to a two-layer channel router, which leads to a 7% reduction in chip height.>

The authors study the problem of 'properly' distributing the set of crossings (i.e., intersection of nets) of a given global routing among the regions. Each region is assigned a quota, being the maximum number of crossings allowed in that region, which depends on its area and its complexity (e.g., the number of nets going through it and the number of terminals it contains). The crossing distribution problem (CDP) is to find a net ordering at each boundary so as to minimize the total number of crossings and to satisfy the quotas. The authors propose an O(mn/sup 2/+m zeta /sup 3/2/) time algorithm for CDP, where m is the number of modules, n is the number of nets, and zeta is the number of crossings.>

Advances in VLSI technology and the increased complexity of circuit designs cause performance to become an increasingly important constraint for layout. The issue of delay optimization during the global routing phase is addressed. This problem is formulated as the construction of a bounded-radius spanning tree for a given pointset in the plane, and a family of effective heuristics is presented. This approach has very good empirical performance with respect to total wirelength, and can be smoothly tuned between the competing requirements of minimum delay and minimum total netlength, as confirmed by extensive computational results which confirm this. Extensions can be made to the graph and Steiner versions of the problem, and a number of open problems are described.>

The topological via minimization problem in a two-layer environment is considered. A set of n two-terminal nets in a bounded region is given. The authors attempt to find a homotopy to assign nets to distinct layers so that no two nets on the same layer cross each other and the number of vias is minimized. A recursive approach in which an optimal solution to a two-sided channel routing problem is used as a basis is used to solve this problem optimally. The notion of partition number K of a circle graph is introduced, and the total running time of the via minimization algorithm is shown to be O((n/K)/sup 2K-2/ log (n/K)), where n is the total number of nets.>

The authors study a generalization of previous results on the boundary single-layer routing (BSLR) problem. In the BSLR problem, there is a planar graph, a collection of terminals on the boundary of the infinite face, and a set of multiterminal nets. A solution of BSLR consists of a set of vertex disjoint trees interconnecting the terminals belonging to the same (multiterminal) net. An algorithm, unifying and generalizing previous BSLR algorithms, to solve an arbitrary instance of BSLR, is presented. Problems involving slidable terminals (i.e. when terminals can slide within a certain range on the boundary) and permutable terminals (i.e. when positions of some terminals (going to the same gate) can be interchanged) are optimally solved. The proposed algorithm runs in O(e) time, where e is the number of edges in the input graph. The results are extended to handle gridless routing environments.>

Consider a given single-layer detailed routing L of a set of two-terminal nets. The authors present necessary and sufficient conditions for a layout to have minimum length under homotopic transformations (i.e., without changing the given global routing). Based on the proposed classification and the notion of line-segment visibility, the authors present an exact algorithm that minimizes the total wire-length of L. The proposed algorithm runs in O(n/sup 2/) time, where n is the number of bends in L. For the class of x-monotone layouts (i.e., each vertical line crosses each wire once at most) an O(n log n) time algorithm is proposed.>

The problem of finding a minimum cut of n arcs on a unit circle is considered. It is shown that this problem can be solved in $\Theta (n \log n)$ time, which is optimal to within a constant factor. If the endpoints of the arcs are sorted, the problem can be solved in linear time. The solution to the minimum cut problem can be used to solve a minimum new facility problem in competitive location and a minimum partition set problem for the intersection model of a circle graph. As a by-product it is also shown that the maximum independent set of n arcs can be obtained in linear time, assuming the endpoints are sorted, which is much simpler than the most recent result of Masuda and Nakajima [SIAMI. Comput., 17 (1988), pp. 41–52].

The problem of stretching a knock-knee layout in the knock-knee mode to ensure its wirability is considered. An optimal algorithm for the problem in two layers is presented. A 4/3 approximation algorithm for the corresponding problem in three layers, shown to be NP-complete, is devised.>

An optimal algorithm for minimizing the number of columns (width) in a three-sided switchbox, when the modules are allowed to slide, is presented. The proposed algorithm runs in O(mn+e log e) time, where m and n are the number of terminals on the top and on the bottom, and e is the total number of feasible alignments (e>

Global routing of multiterminal nets is studied. A novel global router is proposed; each step consists of finding a tree, called a Steiner min-max tree, that is Steiner tree with maximum-weight edge minimized (real vertices represent channels containing terminals of a net, Steiner vertices represent intermediate channels, and weights correspond to densities). An O (min(e loglog e, n/sup 2/)) time algorithm is proposed for obtaining a Steiner min-max tree in a weighted graph with e edges and n vertices. (This result should be contrasted with the NP-completeness of the traditional minimum-length Steiner tree problem). Experimental results on difficult examples, on randomly generated data, on master slice chips, and on benchmark examples from the Physical Design Workshop are included.>

The problem of minimizing the number of power pads, in order to guarantee the existence of a planar routing of multiple power nets, is discussed. A general lower bound is derived, and a heuristic for the general problem is discussed. Several important special cases, including the case of three power nets, are examined, and optimal strategies for pad placement are presented. It is also shown that the general pad minimization problem is NP-complete.>

The layer assignment problem that arises in the design of a multichip module, a high-performance compact package for the interconnection of several hundred chips, is studied. The aim is to place each net in a x-y pair of layers, so as to minimize the number of such pairs. An approximation algorithm, running in O(nd) time is presented for minimizing the number of layers, where n is the number of nets and d is the (two-dimensional) density of the problem.>

Mesh and mesh-of-pyramids implementations of iterative image restoration algorithms are proposed. These implementations are based on a single-step algorithm as well as on a multistep iterative algorithm derived from the single step regularized iterative restoration algorithm. One processor is assigned to each picture element, with local memory depending on the support of the restoration filter. The implementations consist of interprocessor communication and intraprocessor computations. The efficiency of the proposed VLSI algorithms is judged by establishing lower bounds on AT/sup 2/, where A is the area of the VLSI and T is its computation time.>

A study is made of the global routing of multiterminal nets. The authors propose a novel global router. Each step consists of finding a tree, called Steiner min-max tree, that is, a Steiner tree with the maximum-weight edge minimized (real vertices represent channels containing terminals of a net, Steiner vertices represent intermediate channels, and weights correspond to densities). An efficient algorithm is presented for obtaining a Steiner min-max tree, in a weighted graph. Experimental results on difficult examples, randomly generated data, master slice chips, and benchmark examples from the physical design workshop are very promising. (In all cases, previous results have been improved.).>

Article Optimal VLSI architectures for multidimensional DFT Share on Authors: G. Bilardi Department of Computer Science, Upson Hall, Cornell University, Ithaca, NY Department of Computer Science, Upson Hall, Cornell University, Ithaca, NYView Profile , S. W. Hornick Andersen Consulting, Center for Strategic Tech. Res., 100 S. Wacker, Chicago, IL Andersen Consulting, Center for Strategic Tech. Res., 100 S. Wacker, Chicago, ILView Profile , M. Sarrafzadeh Dept. of Elec. Eng. and Comp. Sci., The Technological Institute, Northwestern University, Evanston, IL Dept. of Elec. Eng. and Comp. Sci., The Technological Institute, Northwestern University, Evanston, ILView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 265–272https://doi.org/10.1145/72935.72963Online:01 March 1989Publication History 7citation284DownloadsMetricsTotal Citations7Total Downloads284Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A topological via minimization problem in a two-layer routing environment is examined. The problem of minimizing the number of vias needed to route n two-terminal nets in a bounded routing region is shown to be NP-hard. However, in the case of a two-shore routing region, the topological via minimization problem can be solved in O(n/sup 2/ log n) time. As a basis for the algorithm, a two-chain maximum dominance problem, which is of interest in its own right, is considered, and its applications to other very large-scale integration layout problems are shown.>

We will show that it is NP-Complete to decide whether an arbitrary instance of the channel-routing problem in the knock-knee mode can be laid out optimally. This result is extended to problems (arising in practice) involving nets of bounded degree