Recent advances in LLM agentic systems have improved the automation of offensive security tasks, particularly for Capture the Flag (CTF) challenges. We systematically investigate the key factors that drive agent success and provide a detailed recipe for building effective LLM-based offensive security agents. First, we present CTFJudge, a framework leveraging LLM as a judge to analyze agent trajectories and provide granular evaluation across CTF solving steps. Second, we propose a novel metric, CTF Competency Index (CCI) for partial correctness, revealing how closely agent solutions align with human-crafted gold standards. Third, we examine how LLM hyperparameters, namely temperature, top-p, and maximum token length, influence agent performance and automated cybersecurity task planning. For rapid evaluation, we present CTFTiny, a curated benchmark of 50 representative CTF challenges across binary exploitation, web, reverse engineering, forensics, and cryptography. Our findings identify optimal multi-agent coordination settings and lay the groundwork for future LLM agent research in cybersecurity.

Machine learning (ML) has become integral to cybersecurity applications, e.g., phishing detection, intrusion detection systems, malware analysis, and botnet identification. However, the integration of ML also exposes novel attack surfaces that can be exploited through adversarial machine learning (AML). While prior surveys have examined individual threats or defenses, they often focus narrowly on specific stages, e.g., training or testing. In contrast, in this paper, we provide the first comprehensive survey of adversarial attacks and defenses across the entire ML development life cycle within the cybersecurity domain. Using a structured methodology, we categorize vulnerabilities and countermeasures at each stage, data gathering, model training, testing, deployment, and maintenance, highlighting cross-stage interactions and emerging distributed threat models. Our study addresses key gaps in current defenses, including their limited generalizability and lack of standardized evaluation practices, and identifies promising directions, e.g., lifecycle-aware robustness, distributed resilience, and the integration of statistical with generative methods. Consolidating fragmented research into an end-to-end perspective, this study advances the understanding of AML in cybersecurity and outlines a roadmap for building more trustworthy, and resilient ML-driven security systems.

Current malware (malicious software) analysis tools focus on detection and family classification but fail to provide clear and actionable narrative insights into the malignant activity of the malware. Therefore, there is a need for a tool that translates raw malware data into human-readable descriptions. Developing such a tool accelerates incident response, reduces malware analysts’ cognitive load, and enables individuals having limited technical expertise to understand malicious software behaviour. With this objective, we present MaLAware, which automatically summarizes the full spectrum of malicious activity of malware executables. MaLAware processes Cuckoo Sandbox-generated reports using large language models (LLMs) to correlate malignant activities and generate concise summaries explaining malware behaviour. We evaluate the tool’s performance on five opensource LLMs. The evaluation uses the human-written malware behaviour description dataset as ground truth. The model’s performance is measured using 11 extensive performance metrics, which boosts the confidence of MaLAware’s effectiveness. The current version of the tool, i.e., MaLAware, supports Qwen2.5-7B, Llama2-7B, Llama3.1-8B, Mistral-7B, and Falcon-7B, along with the quantization feature for resource-constrained environments. MaLAware lays a foundation for future research in malware behavior explanation, and its extensive evaluation demonstrates LLMs’ ability to narrate malware behavior in an actionable and comprehensive manner.

Amid the surge of Non-Fungible Tokens (NFTs) in blockchain, this study introduces a meticulous methodology focusing on transaction behaviors to unveil rug pulls — a critical issue impacting financial security and trust in the NFT landscape. Using a Graph Isomorphism Network (GIN) model with 6 behavioral patterns obtained from transaction sequences, we create a “Rug Pull Pattern Matcher” model. We provide a comprehensive analysis by applying the model on two datasets — creator’s transactions from 50 reputable NFT projects and 32 reported rug pulls. Our work utilizes automated labeling to categorize addresses and our analysis reveals several interconnected NFT creator activities. We present an in-depth mapping of fund flows and creator interactions exposing suspicious behaviors like artificial inflation and intricate network collaborations among creators. The results of our proposed model demonstrate the efficacy of our methodology with 75.4% accuracy and 85.9% precision on the dataset of reported rug pulls. This work provides comparative analyses of genuine and malicious creator networks to elucidate their structural differences, helping to identify genuine and potentially fraudulent NFT activities.

The proliferation of advanced detection techniques and the evolution of next-generation firewalls and antivirus engines have led to the increasing sophistication of cyber threats. In this context, malware authors are crafting disguised payloads that mimic benign behavior. To achieve this, the use of Windows signed executables/binaries (Living off the Land Binaries or LOLBins) and libraries has become increasingly relevant as a method to evade antivirus and signature-based detection techniques. These binaries inherently grant attackers a level of trust within the Windows operating system as they are signed by Microsoft. Understanding the specific LOLBins used by different attacks and their variants is crucial for developing effective detection rules and enhanced threat intelligence. Therefore, in this work, we analyze the presence of LOLBins from five distinct cyber attacks through dynamic analysis to determine the ubiquity and role of these Windows signed binaries in these attacks. We observe that the usage of LOLBins is nearly 51% of the payloads across Ransomware, Cryptominers, Advanced Persistent Threats (APTs), Information Stealers, and Remote Access Trojans (RATs)/Trojans. We also identify the distinct roles of the same LOLBins in attack variants in terms of evading defense strategies, downloading payloads, and offering stealth. Notably, ransomware and crypto miner payloads exhibit a higher diversity of utilizing 55 and 30 distinct LOLBins, respectively. Finally, we systematically analyze and compare the usage of LOLBins in Cobalt Strike payloads—a legacy multipurpose tool used by many malware families to evade detection, gather information, and persist within the victim environment. We identify Cobalt Strike to have the highest usage among all categories, at almost 73%.

The explosive growth of non-fungible tokens (NFTs) on Web3 has created a new frontier for digital art and collectibles and an emerging space for fraudulent activities. This study provides an in-depth analysis of NFT rug pulls, the fraudulent schemes that steal investors’ funds. From a curated dataset of 760 rug pulls across 10 NFT marketplaces, we examine these schemes’ structural and behavioral properties, identify the characteristics and motivations of rug pullers, and classify NFT projects into 20 groups based on creators’ association with their accounts. Our findings reveal that repeated rug pulls account for a significant proportion of the rise in NFT-related cryptocurrency crimes, with one NFT creator attempting 37 rug pulls within 3 months. Additionally, we identify the largest group of creators influencing the majority of rug pulls and demonstrate the connection between rug pullers of different NFT projects using the same wallets to store and move money. Our study contributes to understanding NFT market risks and provides insights for designing preventative strategies to mitigate future losses.

Individuals, organizations and nation-states are increasingly falling victim to cyberattacks. A lot of research on how to understand the modus operandi of a cyber attacker through the MITRE ATT&CK framework, CAPEC enumeration and various cyber kill chain frameworks has been available for cyber incident responders for both pre-attack defensive posture preparation as well as post-attack mapping of the indicators. Cybercrime, on the other hand, has a very different set of motives, majorly financial, but also impersonation, harassment and hate crimes, which are targeted mostly towards individuals who are vulnerable. Investigative officers in cyber cells around the world use various investigative processes in their attempt to solve a cybercrime incident, detect the criminal(s), recover the lost money, shut down the accounts of perpetrators, or bring down the cyber-criminal gangs involved in reported cybercrime incidents. However, to the best of our knowledge, there is no framework to map the cybercrime incident narratives to the tactics, techniques and procedures (TTPs) used by cybercriminals, nor are the processes used by cybercrime investigating officers mapped to such TTPs to create a systematic modus operandi for the investigators to solve a cybercrime, cluster multiple crime incidents as attributable to a specific cybercrime operator, or systematically map a set of evidence collected to a pattern of TTPs. In this paper, we present a TTP-based framework for classified cybercrimes to formulate a comprehensive strategy for cybercrime interpretation and action recommendations for law enforcement officers, which can be used as a reference point to establish targeted threat models and incident response methodologies for cybercrime investigations.

The rise in the adoption of blockchain technology has led to increased illegal activities by cybercriminals costing billions of dollars. Many machine learning algorithms are applied to detect such illegal behavior. These algorithms are often trained on the transaction behavior and, in some cases, trained on the vulnerabilities that exist in the system. In our approach, we study the feasibility of using the Domain Name (DN) associated with the account in the blockchain and identify whether an account should be tagged malicious or not. Here, we leverage the temporal aspects attached to the DN. Our approach achieves 89.53% balanced-accuracy in detecting malicious blockchain DNs. While our results identify 73769 blockchain DNs that show malicious behavior at least once, out of these, 34171 blockchain DNs show persistent malicious behavior, resulting in 2479 malicious blockchain DNs over time. Nonetheless, none of these identified malicious DNs were reported in new officially tagged malicious blockchain DNs.

Abstract Due to the importance of Critical Infrastructure (CI) in a nation’s economy, they have been lucrative targets for cyber attackers. These critical infrastructures are usually Cyber-Physical Systems such as power grids, water, and sewage treatment facilities, oil and gas pipelines, etc. In recent times, these systems have suffered from cyber attacks numerous times. Researchers have been developing cyber security solutions for CIs to avoid lasting damages. According to standard frameworks, cyber security based on identification, protection, detection, response, and recovery are at the core of these research. Detection of an ongoing attack that escapes standard protection such as firewall, anti-virus, and host/network intrusion detection has gained importance as such attacks eventually affect the physical dynamics of the system. Therefore, anomaly detection in physical dynamics proves an effective means to implement defense-in-depth. PASAD is one example of anomaly detection in the sensor/actuator data, representing such systems’ physical dynamics. We present EPASAD, which improves the detection technique used in PASAD to detect these micro-stealthy attacks, as our experiments show that PASAD’s spherical boundary-based detection fails to detect. Our method EPASAD overcomes this by using Ellipsoid boundaries, thereby tightening the boundaries in various dimensions, whereas a spherical boundary treats all dimensions equally. We validate EPASAD using the dataset produced by the TE-process simulator and the C-town datasets. The results show that EPASAD improves PASAD’s average recall by 5.8% and 9.5% for the two datasets, respectively.

There are several security tools available to tackle cyber threats, but the sophistication of attacks leads to the failure of defense mechanisms. Among such tools, endpoint security agents are much prominent to safeguard organizations from potential threats. To monitor and investigate systems for unpredictable modifications and proof of tactics, techniques, and procedures (TTP) used by malware writers. In this work, we develop a real-time system behavior monitoring solution. We use three modules - monitoring, analysis, and mapping to counter the threats based on attack patterns. All three modules have their unique mechanism and are interconnected. The monitoring agent is developed for the Windows platform using the C++ programming language, which captures Windows kernel-level system events in a multi-threaded form. It captures critical information such as - network activity, registry, file, accessed paths, processes, etc. The monitoring agent ships the collected events to the analysis module. In the analysis module, we perform analysis in three phases: rule-based, machine learning (ML)-based, and risk-assessment. Rule-based mechanism finds the Indicator of Compromises (IoCs) from the system events related to exploits, web shell, malicious documents, etc. The ML-based analysis gives an overall understanding of normal vs. suspicious behavior. The risk-assessment analysis uses rule-based and ML-based analysis outputs, to provide the risk-score based on the number of IoCs detected and the suspicious behavior predicted. In the mapping phase, we offer an interactive dashboard to the end-user for visualizing all the activities and the analysis outcomes like running processes, suspicious processes, network activities, port accessed, suspicious paths accessed by a single process, etc., using Kibana. The designed tool monitors the system events in near real-time and reports any suspicious activity that helps in mitigating the threats posed to the user. Hence, it acts as a comprehensive security solution with multi-dimensional capabilities.

With the large-scale adaptation of Android OS and ever-increasing contributions in the Android application space, Android has become the number one target of malware writers. In recent years, a large number of automatic malware detection and classification systems have evolved to tackle the dynamic nature of malware growth using either static or dynamic analysis techniques. Performance of static malware detection methods degrade due to the obfuscation attacks. Although many benchmark datasets are available to measure the performance of malware detection and classification systems, only a single obfuscated malware dataset (PRAGuard) is available to showcase the efficacy of the existing malware detection systems against the obfuscation attacks. PRAGuard contains outdated samples till March 2013 and does not represent the latest application categories. Moreover, PRAGuard does not provide the family information for malware because of which PRAGuard can not be used to evaluate the efficacy of the malware family classification systems.

Different malicious activities occur in cryptocurrency-based permissionless blockchains such as Ethereum and Bitcoin. Some activities are due to the exploitation of vulnerabilities which are present in the blockchain infrastructure, some activities target its users through social engineering techniques, while some activities use it to facilitate different malicious activities. Since cryptocurrency-based permissionless blockchains provide pseudonymity to its users, bad actors prefer to carry out transactions related to malicious activities on them. Towards this, we aim at automatically flagging blockchain accounts as suspects that indulge in malicious activities, thus reducing the unintended support that cryptocurrency-based permissionless blockchains provide to malicious actors. We first use the cosine similarity (CS) metrics to study the similarities between the feature vector of accounts associated with different malicious activities and find that most of the malicious activities associated with the Ethereum blockchain behave similarly. We then use the K-Means clustering algorithm to check if accounts associated with similar malicious activities cluster together. We also study the effect of bias on the performance of a machine learning (ML) algorithm, due to the number of accounts associated with malicious activity. We then compare the different state-of-the-art models and identify that Neural Networks (NNs) are resistant to bias associated with a malicious activity and are also robust against adversarial attacks. The previously used ML algorithms for identifying malicious accounts also show bias towards an over-represented malicious activity.

Over the past few years, Android has become one of the most popular operating systems for smartphones as it is open-source and provides extensive support for wide variety of applications. This has led to an increase in the number of malware targeting Android devices. The lack of robust security enforcement in Play Store along with the rapid increase in the number of new Android malware presents a scope for a variety of diverse malicious applications to spread across devices. Further-more, Android allows installation of an application from unver-ified sources (e.g., third-party market and sideloading), which opens up other ways for mal ware to infect the smartphones. This paper presents DeepDetect that enables on-device malware detection by employing a machine learning based model on static features. With effective feature engineering, DeepDetect can be used on-device. To classify an Android application as malware, it takes ~5.32 seconds, which is 2.23X faster than API based malware detector, while consuming 0.45 % (for 50 applications) of total device energy. DeepDetect provides a malware detection rate of 99.9% for known malware with a 0.01 % false-positive rate. For unseen/new samples, it detects more than 97 % mal ware with a false-positive rate of 1.73%. Further, in the presence of obfuscated malware, DeepDetect correctly detects 95.57 % of malware samples. We have also evaluated our model against the Pegasus malware sample and with a new dataset after removing the potential biases across space and time.

With the increased popularity and wide adoption of Android as a mobile OS platform, it has been a major target for malware authors. Due to unprecedented rapid growth in the number, variants, and diversity of malware, detecting malware on the Android platform has become challenging. Beyond the detection of a malware, classifying the family the malware belongs to, helps security analysts to reuse malware removal techniques that is known to work for that family of malware. It takes manual analysis if a malware belongs to an unknown family. Therefore, classifying malware into exact family is important. This paper presents a technique and tool named MAPFam that applies machine learning on static features from the Manifest file and API packages to classify an Android malware into its family. This work is premised on a starting hypothesis that features extracted from API packages rather than on API calls lead to more precise classification. Our experiments indeed shows that API package based models provides ∼1.63X more accurate classification compared to an API call based method. Our machine learning based malware family classification system uses API packages, requested permissions, and other features from the Manifest files. The proposed family classification system achieves accuracy and average precision above 97% for the top 60 malware families by using only 81 features with 97.55% of model reliability rate (Kappa score). The experimental results also shows that MAPFam can perfectly identity 36 malware families.

Controller area network (CAN) is a widely used protocol that allows communication among electronic control units (ECUs) in automotive electronics. It was extended to CAN with flexible data-rate (CAN-FD) to meet the increasing demand for bandwidth generated by the growing number of features in modern automobiles. The signal-to-frame packing problem has been studied in the literature for both CAN and CAN-FD. In this paper, we propose and formulate the signal offset assignment problem (SOAP) in CAN-FD to improve the bus utilization during frame packing. We propose two algorithmic themes to solve SOAP and establish their worst case performance guarantees. The first is a general approximation framework (GAF) which can use any approximation algorithm for the makespan minimization problem (MMP) in multiprocessor systems. Its performance guarantee is the product of the performance guarantee of the MMP algorithm and the number of distinct periods in the frame. The second is a 2-D strip packing-based framework (2DSPF) which uses the bottom left fill algorithm for 2-D strip packing. The performance guarantee is 2G , where G is the minimum number of groups into which the set of signals can be partitioned so that the periods of the signals in the same group form a geometric series. The experimental results for GAF and 2DSPF indicate that by carefully assigning offsets for signals in frame packing schemes, one can achieve about 10.83% improvement in bus utilization in CAN-FD systems.

My tenure as the Editor-in-Chief of this prestigious journal is coming

In the book Guns, Germs, and Steel: The Fates of Human Societies, Professor Jared Diamond told us that germs played a significant role in shaping human societies in different parts of the world.Appearances of new germs, outbreaks of viral diseases, and intermittent pandemic episodes have punctuated human history periodically in the past.The current COVID-19 crisis is a unique experience for all of us.It has thrown tremendous challenges to our way of life as we knew it before this crisis.It seems that the nature is sending us a strong message-to re-evaluate our priorities, our way of life, our science and technology investments, and overall, our contribution to the structure and direction of the societies we live in.Some of these issues are not specific to the readership of this journal, but embedded computing researchers are also part of the society, and if anything, this crisis is pointing to the dependence of the survival of individuals on the larger society and how it functions.We must rethink and reshape the societies as the crisis recedes and a tendency to go back to the usual norms tries to overpower us.Even though some of us are living detached lives with our professional concerns around computing and science in general, the crisis must shake us to the awakening that society needs reshaping in a radical new way-otherwise, there is no hope for the survival of us as a species, no matter how much technological progress we make.We must endeavour to influence science and technology priorities, research investments, public health infrastructure, and most importantly the economic models of tomorrow-as the status quo over the past decades is failing us in every way during the crisis.Having said that much, I want to make some observations regarding the scope of embedded computing technology during the current pandemic.One of the most challenging parts of managing the crisis has been in the medical field.Due to the cumulative effects of continual reduced public expenditure on national health infrastructure and welfare of citizens, we find ourselves in a severe shortage of lifesaving equipment.Ventilators for patients with severe respiratory incapacitation, the test kits to diagnose patients, and the personal protective equipment that would assist health workers with active monitoring of hazard are either in extreme short supply or need to be manufactured on demand when our hospitals run out of them, endangering lives.The medical professionals are the frontline combatants in a war against the germ, but they are handicapped by the lack of ICU beds, ventilators, test kits, and their own protective gear.Under duress, we find that many universities around the world, including my own, have come up with design for ventilators overnight and started producing them in a cottage industry mode.Even though these are not of the expensive calibrated variety built by medical equipment manufacturers, it is amazing that engineers around the world rose to the occasion and fashioned mobile phones and other processor boards at their disposal to program the sensing and actuation of mechanical components to build lifesaving equipment.This is a fine example of embedded computing at the hour of need, built

No abstract available.

No abstract available.

No abstract available.

No abstract available.

As I write this editorial, a lot has been happening around us.Apple's secure enclave processor firmware has been decrypted; face recognition-based secure identification of iPhone X has been hacked, with relatively inexpensive masks, apparently; the Uber data breach compromised the privacy of 57 million people; the Equifax breach compromised even a larger number of people; and new Android Trojan malware were discovered in the Google Play store.These are but a few examples that have been published in the media.A lot more is happening and being suppressed.News reports suggest that Uber might have paid hackers to suppress a data breach.Other reports indicate that even an Indian telecom provider might have paid hackers for similar reasons.In India, a cloud of suspicion over electronic voting machines, popularly known as EVMs, have gathered after a few reports surfaced on all votes automatically going to a specific party.Even today, reports of that sort of compromise are coming in, as there is a hotly contested regional election taking place in India today.While the Election Commission of India has denied any such possibilities, they have not been forthcoming in offering experts to open these EVM machines and probe the hardware, firmware, and possible attack surfaces, leaving a section of politicians and the public suspicious.Given that Twitter bots and social media bots have been unleashed by the millions to sway public opinions, creating and propagating fake news and challenging the normal democratic processes, it is a scary new world that we are faced with today.Continually extending our digital footprint and moving all political, business, financial, social, and transactional activities to the digital world in search of efficiency, are we not exposing ourselves to an unknown future?Why are these relevant to embedded computing?This is a journal of embedded computing, and in my editorial comments, I always seem to be obsessed with cyber security over all other challenges germane to embedded computing.Is it intentional to attract more submissions in the embedded security domain?My answer is that, subconsciously, possibly, but there is a good logical reason for this fear and concern.Furthermore, most devices that we find vulnerable, the same devices that affect our lives and society, are embedded computing devices-be it mobile phones, voting machines, automotives, avionic controls, Internet of Things (IoT)-based automation, sensors and control systems in utilities, or medical devices such as pacemakers or insulin pumps.While a large-scale data breach usually concerns IT systems, even there we saw a tangled web of cyber physical sensor network security affecting IT security.Take, for example, the Target data breach.The network for HVAC system monitoring was breached and became the conduit to propagate malware to point-of-sales machines, which led to the stealing of credit card information while being swiped for authorization.Compounding these vulnerabilities and mounting threats, insider threats are also increasing through social engineering and other human-centric processes.A high-privilege system administrator might compromise individuals unless the system is designed to be robust against insider attacks.We have evolved our IT systems with the assumption of trusted central authority, or a trusted third party, and only became aware of the large percentage of internal attack incidents in major breaches.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

The Controller Area Network with Flexible Data-Rate (CAN-FD) is a new communication protocol to meet the bandwidth requirements for the constantly growing volume of data exchanged in modern vehicles. The problem of frame packing for CAN-FD, as studied in the literature, assumes a single sub-system where one CAN-FD bus serves as the communication medium among several Electronic Control Units (ECUs). Modern automotive electronic systems, on the other hand, consist of several sub-systems, each facilitating a certain functional domain such as powertrain, chassis and suspension. A substantial fraction of all signals is exchanged across sub-systems. In this work, we study the frame packing problem for CAN-FD with multiple sub-systems, and propose a two-stage optimization framework. In the first stage, we pack the signals into frames with the objective of minimizing the bandwidth utilization. In the second stage, we extend Audsley's algorithm to assign priorities/identifiers to the frames. In case the resulting solution is not schedulable, our framework provides a potential repacking method. We propose two solution approaches: (a) an Integer Linear Programming (ILP) formulation that provides an optimal solution but is computationally expensive for industrial-size problems; and (b) a greedy heuristic that scales well and provides solutions that are comparable to optimal solutions. Experimental results show the efficiency of our optimization framework in achieving feasible solutions with low bandwidth utilization. The results also show a significant improvement over the case when there is no cross-domain consideration (as in prior work).

Controller Area Network (CAN) is a widely used protocol that allows communication among Electronic Control Units (ECUs) in automotive electronics. It was extended to CAN-FD (CAN with Flexible Data-rate) to meet the increasing demand for bandwidth utilization caused by the growing number of features in modern automobiles. The signal-to-frame packing problem has been studied in literature for both CAN and CAN-FD. In this work, we propose and formulate, for the first time, the signal offset assignment problem (SOAP) in a frame in order to improve the bus bandwidth utilization. We prove that SOAP is NP-complete. We propose a general approximation framework (GAF) for SOAP which can use any approximation algorithm for the makespan minimization problem (MMP) in multiprocessor systems. We derive the performance guarantee provided by GAF as a function of the performance guarantee of the approximation algorithm for MMP and the number of signal periods in the frame. We demonstrate the efficacy of our approach through experiments using three different algorithms (two approximation algorithms and an integer linear programming formulation) for MMP in GAF. Our results indicate that by using offsets for signals in frame packing schemes, one can achieve about 10.54% improvement in bandwidth utilization (on a single bus) in CAN-FD systems.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

Model-Based Engineering (MBE) is a promising approach to cope with the challenges of designing the next-generation automotive systems. The increasing complexity of automotive electronics, the platform, distributed real-time embedded software, and the need for continuous evolution from one generation to the next has necessitated highly productive design approaches. However, heterogeneity, interoperability, and the lack of formal semantic underpinning in modeling, integration, validation and optimization make design automation a big challenge, which becomes a hindrance to the wider application of MBE in the industry. This paper briefly presents the interoperability challenges in the context of MBE and summarizes our current contribution to address these challenges with regard to automotive control software systems. A novel model-based formal integration framework is being developed to enable architecture modeling, timing specification, formal semantics, design by contract and optimization in the system-level design. The main advantages of the proposed approach include its pervasive use of formal methods, architecture analysis and design language (AADL) and associated tools, a novel timing annex for AADL with an expressive timing relationship language, a formal contract language to express component-level requirements and validation of component integration, and the resulting high assurance system delivery.

The concept of liquid clocks introduced in this paper is a significant step towards a more precise compile-time framework for the analysis of synchronous and polychromous languages. Compiling languages such as Lustre or Signal indeed involves a number of static analyses of programs before they can be synthesized into executable code, e.g., synchronicity class characterization, clock assignment, static scheduling or causality analysis. These analyses are often equivalent to undecidable problems, necessitating abstracting such programs to provide sound yet incomplete analyses. Such abstractions unfortunately often lead to the rejection of programs that could very well be synthesized into deterministic code, provided abstraction refinement steps could be applied for more accurate analysis. To reduce the number of false negatives occurring during the compilation process, we leverage recent advances in type theory - with the definition of decidable classes of value-dependent type systems - and formal verification, linked to the development of efficient SAT/SMT solvers, to provide a type-theoretic approach that considers all the above analyses as type inference problems. To simplify the exposition of our new approach in this paper, we define a refinement type system for a minimalistic, synchronous, stream-processing language to concisely represent, analyze, and verify logical and quantitative properties of programs expressed as stream-processing data-flow networks. Our type system provides a new framework for representing logical time (clocks) and scheduling properties, and to describe their relations with stream values and, possibly, other quantas. We show how to analyze synchronous stream processing programs (à la Lustre, Signal) to enable previously described analyses involved in compiling such programs. We also prove the soundness of our type system and elaborate on the adaptability of this core framework by outlining its extensibility to specific models of computations and other quantas.

In modern System on Chip (SoC) designs, the multi-cycle delays on long interconnects between synchronously clocked IP blocks are accommodated by latency insensitive protocols (LIP) through extra valid/stall handshakes between components and additional logic blocks called relay stations. The use of handshaking interconnects and relay stations leads to area and latency penalties, that must be minimized for cost effective SoC designs. Interconnected IP blocks with certain graph topology have periodic behaviors that can be exploited to remove the need for handshake interconnects. Unfortunately, the periodic schedule may not exist for any LIS designs consist of two or more strongly connected components. Some of these systems are not bounded without back pressure. In the past, back pressure between SCCs has always been implemented as stall signals in the backward direction, and they are required to prevent overflow. In this paper, we propose an LIS design optimization algorithm which computes a minimum set of back pressure arcs required between SCCs. We model an LIS by a partial back pressure graph (PBPG) and show that the boundedness of a PBPG can be verified by checking the reachability in its strongly connected component graph (SCCG). Based on this, we formulate the problem of finding a minimum set of back pressure arcs (MBPA) and show that this problem can be reduced to the Minimum Cost Arborescence (MCA) problem for directed graphs. This allows us to obtain a polynomial time algorithm for synthesizing a minimum cost LIS implementation starting from a synchronous model of the original system. After adding back pressure arcs, we develop a localized Mixed Integer Linear Programming (LMILP) approach to optimize the throughput of the resulting LIS. This approach scales better than existing MILP-based throughput optimization techniques. In addition, we also provide an implementation of the LIS which refines its PBPG model. To the best of our knowledge, this is the first effort that considers the optimization of back pressure and throughput together in the design of latency insensitive systems.

No abstract available.

No abstract available.

Schizoid Design

No abstract available.

Cyber physical systems are characterized by continuous interaction between digital control systems and physical systems. To design critical control software that is to be used in control systems, a modeldriven correct-by-construction approach is preferable. Modeling languages based on synchronous model of time - such as Simulink, State Chart, Esterel, Lustre etc., are often used for sequential software synthesis and languages with a polychronous timing model such as Signal, MRICDF (Multi-Rate Instantaneous Channel-connected Data Flow) etc., are often used for concurrent software synthesis. The interfaces of such software to the real world are through digital signals that are often sampled quantities of physical entities - such as velocity, acceleration, pressure etc. Standard type systems available in programming or modeling languages assign traditional data types such as float, real etc., to these signals. Modelers might mistakenly connect two signals with the same traditional data types but representing different physical entities leading to critical bugs in the synthesized software. Early detection of such mistakes require enhanced type system and type checking algorithms. In this work, we attempt to extend the type system of the polychronous modeling language MRICDF and propose type inference techniques that consider the physical dimensions and units of the signals along with the data types. We also propose an SMT (Satisfiability Modulo Theories) based verification approach that verifies type consistency and provides invariants under which the type consistency is upheld.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

The functionality of Fused multiply add (FMA) design can be formally verified by comparing its register transition level (RTL) implementation against its system level specification often modeled by C/C++ language using sequential equivalent checking (SEC). However, C-RTL SEC does not scale for FMA because of the huge discrepancy existed between the two models. This paper analyzes the dissimilarities and proposes two intermediate models, one abstract RTL and one rewritten C model to bridge the gap. The original SEC proof are partitioned into three sub-proofs among intermediate models where a variety of simplification techniques are applied to further reduce the complexity. Experiments from an industry project show that with the two intermediate models, the SEC proof is complete and scalable for FMA design.

This paper presents an embedding of polychronous programs into synchronous ones. Due to this embedding, it is not only possible to deepen the understanding of these different models of computation, but, more importantly, it is possible to transfer compilation techniques that were developed for synchronous programs to polychronous programs. This transfer is nontrivial because the underlying paradigms differ more than their names suggest: Since synchronous systems react deterministically to given inputs in discrete steps, they are typically used to describe reactive systems with a totally ordered notion of time. In contrast, polychronous system models entail a partially ordered notion of time, and are most suited to interface a system with an asynchronous environment by specifying input/output constraints from which a deterministic controller may eventually be refined and synthesized. As particular examples for the mentioned cross fertilization, we show how a simulator and a verification backend for synchronous programs can be made available to polychronous specifications, which is a first step toward integrating heterogeneous models of computation.

Polychronous specifications express concurrent, multi-clocked models which capture multiple threads of computation operating relatively asynchronous to each other. A clock of a variable in this context, is the totally ordered set of instants at which events occur on that variables. However, the notion of instant here is logical as opposed to real-time instants. The instants of different clocks may be partially ordered. The executable code synthesis from Polychronous specifications relies on computation of schedules through clock calculus. Unfortunately, it is often hard to distinguish from true causal loops which cause deadlocks from apparent causal loops which do not. The SIGNAL compiler in the Polychrony tool-set currently rejects all programs with apparent causal loops, thus rejecting a large set of valid specifications. A recently developed polychronous formalism MRICDF and its tool-set EmCodeSyn do the same. Even in the Polychrony literature, the deadlock causing loop detection based on Boolean satisfiability is not enough to discern all possible false loops, thereby still rejecting a lot of valid specifications. In order to not reject programs whose apparent loops are never realizable, a theory of reals or integers or other data types are required. In this paper, we formulate the detection of false loops in MRICDF as a decision problem in Satisfiability Modulo Theory (SMT). Due to recent interests in SMT solvers, a number of efficient solvers are available which offer a greater expressiveness in dealing with non Boolean constraints and allow us to discern false loops from realizable causalities in reasonable computation time. This paper proposes an SMT based synthesis technique which demonstrates that several polychronous specifications rejected by the Polychrony/EmCodeSyn synthesis tools due to their inability to identify only true causal loops, can be synthesized as correct sequential embedded software.

THE idea of this special section dawned on us during various discussions on the recent trends in computer system design throughout the 2008-2009 academic year when one of the editors spent a sabbatical year at INRIA hosted by the other editor. Cyber Physical System (CPS) was the most recent buzz word replacing the ‘hybrid systems’, and the ‘Science of Design’ (SoD) was the other buzz word on its way out to the perished land of unfashionable terminologies. In the realm of cyber physical systems there had been a lot of foundational developments under the guise of hybrid systems since the mid-nineties. The science of design, another terminology coined at the US National Science Foundation (NSF) somehow remained within the traditional programming language design community and did not get a wider acceptance. Within cyber physical systems, however, there are special classes of systems which are safety critical such as avionics, automotive, space mission systems, missile control, smart grid, industrial process control or SCADA etc. This is the class of systems that interested us the most. We realized that since many of these are domain specific, the engineers who design them are not necessarily computer scientists, and they could be from any other engineering field such as aerospace, electrical, mechanical, power systems, control and so on. The question that naturally comes up as to how they collaborate with the computer scientists who develop the foundations of system design especially systems that have digital control with analog environments which are very common in most safety-critical systems. So we appropriated the term “Science of Design” and termed the foundational aspect of such design as the science, and the domain specific engineering as the application of science. Next we talked to some of our colleagues who were involved in designs of unmanned vehicle systems. It was hoped that a strong contribution to this special issue could be obtained from such colleagues. One would assume that major requirements on the cyber components of such unmanned vehicles must be low power consumption, small form-factor, reliability, verifiability, etc. A paper describing how these requirements interplay with their system design approach, and how the physical system design influences the requirements of the cyber parts and the control algorithms, would have been a great contribution. It turned out that no integrated approach was followed by these designers. Intel x86 processors were purchased (a power hungry one), and an off-the-shelf real-time Linux was used as an execution environment, while MATLAB based control algorithm models were provided to C programmers to create the software. Disappointed by the lack of an integration of science of design into the engineering, we spoke to a number of researchers at a number of defense labs, and contractors, and heard very similar ‘separation of concern’ stories. The safety-critical systems that we were concerned with had strong coupling and interactions between one or more physical environments and a number of cyber or computing components. Evolution of the physical environments over time and space, described by their trajectories in continuous state spaces, are modeled by parameters whose evolution is best captured with continuous dynamical systems. Some of these parameters are controllable by the cyber components, and some evolve based on the dynamics of the physical worlds. The cyber components usually sample some or all of these parameters based on Nyquist criteria, and actuate robust feedback control over controllable parameters. This is often called digital control because the continuously varying parameters are sampled and discretized, while the control algorithms process the information to create control actuations in the form of discrete signals. The feedback control affects the trajectory in the physical state space. Specifically, robust control algorithms make sure that the planned trajectories are tracked by the physical system as accurately as possible, regardless of various uncertainties and exogenous disturbances. Before digital computers were cost effective, much of the control in many such systems were analog and mechanical in nature. This meant that the control components and the physical world together formed a complex dynamical system. The analysis of such system was within the realm of continuous mathematics. However, CPS systems have a dichotomy (between the continuous and the discrete) which poses challenges to their algorithmic development, proof of stability and robustness, etc. On the other hand, there is a tremendous opportunity due to the exponential effects of Moore’s law, making computing exponentially faster, cheaper, and smaller in size. However, the implementation of the control algorithms in hardware and/or software is often distributed in nature (digital signal processing, control computation for a large number of controllable parameters, and real time requirements may necessitate the use of a large number of processors, e.g. a modern automotive vehicle has more than 80 microcontrollers and processors). To make such hardware/software optimized and correct, one has to take care of concurrency issues, timing issues, power vs. performance trade-offs, and most importantly eliminate any redundant sampling or computation. Unfortunately, since such systems are often safety-critical (avionics, automotive, IEEE TRANSACTIONS ON COMPUTERS, VOL. 60, NO. 8, AUGUST 2011 1057

Multi-clocked synchronous (a.k.a. Polychronous) specification languages do not assume that execution proceeds by sampling inputs at predetermined global synchronization points. The software synthesized from such specifications are paced by arrival of certain inputs, or evaluation of certain internal variables. Here, we present an alternate polychronous model of computation termed Multi-rate Instantaneous Channel connected Data Flow (MRICDF) actor network model. Sequential embedded software from MRICDF specifications can be synthesized using epoch analysis, a technique proposed to form a unique order of events without a reference time line. We show how to decide on the implementability of MRICDF specification and how additional epoch information can help in synthesizing deterministic sequential software. The semantics of an MRICDF is akin to that of SIGNAL, but is visual and easier to specify. Also, our prime implicate based epoch analysis technique avoids the complex clock-tree based analysis required in SIGNAL. We experimented with the usability of MRICDF formalism by creating EmCodeSyn, our visual specification and synthesis tool. Our attempt is to make polychronous specification based software synthesis more accessible to engineers, by proposing this alternative model with different semantic exposition and simpler analysis techniques.

The main objective of this paper is to speed up the simulation performance of SystemC designs at the RTL abstraction level by exploiting the high degree of parallelism afforded by today's general purpose graphics processors (GPGPUs). Our approach parallelizes SystemC's discrete-event simulation (DES) on GPGPUs by transforming the model of computation of DES into a model of concurrent threads that synchronize as and when necessary. Unlike the cooperative threading model employed in the SystemC reference implementation, our threading model is capable of executing in parallel on the large number of simple processing units available on GPUs. Our simulation infrastructure is called SCGPSim and it includes a source-to-source (S2S) translator to transform synthesizable SystemC models into parallelly executable programs targeting an NVIDIA GPU. The translator retains the simulation semantics of the original designs by applying semantics preserving transformations. The resulting transformed models mapped onto the massively parallel architecture of GPUs improve simulation efficiency quite substantially. Preliminary experiments with varying-sized examples such as AES, ALU, and FIR have shown simulation speed-ups ranging from 30× to 100×. Considering that our transformations are not yet optimized, we believe that optimizing them will improve the simulation performance even further.

Latency insensitive protocols (LIP) were originally based on valid/stall handshakes between components and relays stations. However, for designs whose connection graph is a single strongly connected component(SCC), it was shown that static scheduling of computation achieves better throughput. Unfortunately, for a system composed of multiple SCCs such global static scheduling is not possible. Recent work has shown how to minimize back pressure (stall) based flow control for such systems. However, that solution does not necessarily achieve optimal throughput because it only minimizes back-pressure without attempting to optimize throughput. Throughput optimizing solutions for latency insensitive systems also exists, which require a mixed Integer Linear Programming (MILP) solution that inevitably does not scale for large systems. Moreover, that throughput optimizing solution uses back pressure for every connection leading to area overhead and further interconnect routing issues. In this paper, we consider an optimization technique for the synthesis of latency insensitive systems. In particular, we consider a synchronous hardware system which is composed of multiple SCCs. We provide algorithm for synthesizing a latency insensitive implementation which minimizes back-pressure while maximizing throughput. Our approach scales because we formulate MILP whose size is significantly smaller than that of the previous throughput optimizing MILP formulation. To the best of our knowledge, this is the first optimization technique considering both back pressure and throughput of latency insensitive system in the literature.

Concurrent Action-Oriented Specifications (CAOS) model the be- havior of a synchronous hardware circuit as asynchronous guarded actions at an abstraction level higher than the Register Transfer Level (RTL). Previous approaches always considered the compilation of CAOS, which includes a transformation of the under-lying model of computation and the scheduling of guarded actions per clock cycle, as a tightly integrated step. In this paper, we present a new compilation procedure, which separates these two tasks and translates CAOS models to synchronous guarded actions with an explicit interface to a scheduler. This separation of con- cerns has many advantages, including better analyses and integration of custom schedulers. Our method also generates assertions that each scheduler must obey that can be fulfilled by algorithms for scheduler synthesis like those developed in supervisory control. We present our translation procedure in detail and illustrate it by various examples. We also show that our method simplifies for- mal verification of hardware synthesized from CAOS specifications over previously known formal verification approaches.

Most scheduling based latency insensitive designs in the literature focus on systems whose graphical representation is a single strongly connected component (SCC), where a hand-shake based protocol can be replaced by periodic clock gating through ASAP scheduling. However, for systems that are represented as interconnected SCCs, `back pressure', always implemented as the `stall' signal in the backward directions between SCCs, is required to prevent overflow. In this paper, we formulate the problem of finding a minimum set of back pressure edges. We show that this problem can be reduced to the Minimum Cost Arborescence (MCA) problem for directed graphs. This allows us to obtain a polynomial time algorithm for synthesizing a minimum cost latency insensitive implementation starting from a synchronous model of the original system. We also show that implementing back pressure edges for every inter-SCC connection, as done in a regular hand-shake based protocol, is inferior for the overall system's throughput. Our approach provides a formal framework for converting a synchronous model into a latency insensitive implementation with a minimum number of inter-SCC back pressure edges and for leveraging periodic clock based scheduling of intra-SCC latency insensitivity.

editorial Free Access Share on Guest editorial: IEEE/ACM symposium on nanoscale architectures (NANOARCH07) Editor: Sandeep Shukla Virginia Polytechnic and State University, Blacksburg, VA Virginia Polytechnic and State University, Blacksburg, VAView Profile Authors Info & Claims ACM Journal on Emerging Technologies in Computing SystemsVolume 5Issue 1January 2009 Article No.: 1pp 1–4https://doi.org/10.1145/1482613.1482614Online:03 February 2009Publication History 0citation640DownloadsMetricsTotal Citations0Total Downloads640Last 12 Months42Last 6 weeks1 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Kahn process networks (KPNs) provide a model of computation for streaming audio, video and various multimedia applications. However, the KPN model consists of unbounded FIFOs between these communicating processes which need to be realized by other means. Application of a design transformation process to a KPN style specification towards a Globally asynchronous locally synchronous (GALS) implementation is one way of achieving this. Furthermore, this transformation process needs to preserve the Kahn principle. In this paper, our main contribution is the presentation of one such refinement based design transformation that preserves the Kahn principle. We present correctness preserving transformation towards a lookup-based architecture where the communication between processes is facilitated by a shared on-chip lookup storage structure. This refinement methodology is generic, and various alternate schemes of GALS implementation can be derived.

In order to exploit the emerging multi-core processors, creating multi-threaded applications is going to be a necessity. However, resolving concurrency, synchronization, and coordination issues, and tackling the non-determinism germane in multi-threaded software is extremely difficult. Ensuring deterministic behavior and correctness with respect to the specification is necessary for safe execution of such code. It is desirable to synthesize multi-threaded code from formal specifications using a provably 'correct-by- construction' approach. In the past, reasonable success has been achieved in the 'correct-by-construction' sequential software synthesis for embedded reactive systems from synchronous programming models. Here we target deterministic multi-threaded software synthesis from deterministic specifications, such that the behavior of the code is semantically equivalent to that of the specification. We choose the polychronous model of computation for specification because (i) such specifications are multi-rate, reactive, concurrent and can be made deterministic through constraints on the environment, and (ii) formal verification methodologies and tools exist for such specifications. In this paper, we analyze under what condition a polychronous specification can be synthesized into multi-threaded C-code preserving its semantics. We also discuss how the synchronous data flow graph structure for a polychronous specification can be used to infer the threading structure of the resulting C-code.

SystemC's growing community for system-level design exploration is a result of SystemC's capability of modeling at register transfer level (RTL) and above RTL abstraction levels. However, a synthesis path from SystemC at abstraction layers above RTL is still in its infancy. A recent extension of SystemC, which is called Bluespec-SystemC electronic system level (BS-ESL), counters this difficulty with itsmodelofcomputationemploying atomic rule-based specifications and synthesis to Verilog. In order to simulate a model consisting of one part designed in SystemC and another using BS-ESL, we require an interoperability semantics and implementation of such a semantics. To illustrate the problem, we formalize the simulation semantics of BS-ESL and discrete-event simulation of RTL SystemC, and provide a solution based on this formalization.

With increasing levels of integration of multiple processing cores and new features to support software functionality, recent generations of microprocessors face difficult validation challenges. The systematic validation approach starts with defining the correct behaviors of the hardware and software components and their interactions. This requires new modeling paradigms that support multiple levels of abstraction. Mutual consistency of models at adjacent levels of abstraction is crucial for manual refinement of models from the full chip level to production register transfer level, which is likely to remain the dominant design methodology of complex microprocessors in the near future. In this paper, we present microprocessor modeling and validation environment (MMV), a validation environment based on metamodeling, that can be used to create models at various abstraction levels and to generate most of the important validation collaterals, viz., simulators, checkers, coverage, and test generation tools. We illustrate the functionalities in MMV by modeling a 32-bit reduced instruction set computer processor at the system, instruction set architecture, and microarchitecture levels. We show by examples how consistency across levels is enforced during modeling and also how to generate constraints for automatic test generation.

Reusing Intellectual Property (IP)-cores accompanied by automated generation of the glue-logic, and automated composability checks can help designers to create efficient system-level models quickly and correctly for fast design space exploration. Furthermore, with the rise of multiple transaction level and register-transfer level abstractions, constructing models with mixed abstraction levels is also important. A framework that allows designers to: 1) describe the structure of components, their interfaces, and their interactions, with a semantically rich visual frontend; 2) automatically select IPs from a component library-based on sound-type theoretic principles; and 3) perform constraint based checks for composability, is highly desirable in this context. A metamodel based framework brings forth further advantages. It helps in: 1) providing rigorous semantics to the visual models; 2) imposing restrictions on the model and on interactions between components through constraints expressed in a constraint language; and 3) enabling type-checking and inference-based facilities. Furthermore, using XML-based schemas to store and process meta-information about the IPs as well as the schematic visual model, allows for an IP selection and integration methodology using existing XML processing tools. With these in mind, we present MCF, a metamodeling-based component composition framework for SystemC-based IP core composition at multiple and mixed abstraction levels, with all the advantages stated above.

Composing intellectual property (IP) blocks running at different clock speeds over asynchronous communication links for a system-on-chip (SoC) design is a challenging task, especially for ensuring the functional correctness of the overall design. In this paper, we propose a trace-based framework that helps in identifying a class of IPs that can be composed to ldquocorrect-by-constructionrdquo globally asynchronous locally synchronous (GALS) designs, and their correctness is maintained with respect to their synchronous compositions. Our notion of correctness is latency equivalence. Latency equivalence means that the order of valid values is same on the corresponding signals in the synchronous as well as asynchronous compositions. We also provide a description of the protocol to be inserted between the IPs to obtain this equivalence.

Functional test generation for dynamic validation of current system level designs is a challenging task. Manual test writing or automated random test generation techniques are often used for such validation practices. However, directing tests to particular reachable states of a SystemC model is often difficult, especially when these models are large and complex. In this work, we present a model-driven methodology for generating directed tests that take the SystemC model under validation to specific reachable states. This allows the validation to uncover very specific scenarios which lead to different corner cases. Our formal modeling is done entirely within the Microsoft SpecExplorer tool to describe the specification of the system under validation in the notation of AsmL. We also exploit SpecExplorer's abilities for state space exploration for our test generations, and its APIs for connecting the model to implementation programs to drive the validation of SystemC models with the generated test cases.

Functional validation of modern microprocessors is an important and complex problem. One of the problems in functional validation is the generation of test cases that has higher potential to find faults in the design. We propose a model based test generation framework that generates tests for design fault classes inspired from software validation. There are two main contributions in this paper. Firstly, we propose a microprocessor modeling and test generation framework that generates test suites to satisfy modified condition decision coverage (MCDC), a structural coverage metric that detects most of the classified design faults as well as the remaining faults not covered by MCDC. Secondly, we show that there exists good correlation between types of design faults proposed by software validation and the errors/bugs reported in case studies on microprocessor validation. We demonstrate the framework by modeling and generating tests for the microarchitecture of VESPA, a 32-bit microprocessor. In the results section, we show that the tests generated using our framework's coverage directed approach detects the fault classes with 100% coverage, when compared to model-random test generation

The growing SystemC community for system level design exploration is a result of SystemC's capability of modeling at RTL and above RTL abstraction levels. However, managing shared state concurrency using multi-threading in large SystemC models is error prone. A recent extension of SystemC called Bluespec-SystemC (BS-ESL) counters this difficulty with its model of computation employing atomic rule-based specifications. However, for simulating a model that is partly designed in SystemC and partly using BS-ESL, an interoperability semantics and implementation of such a semantic is required. This paper views the interoperability problem as an abstraction gap closure problem. To illustrate the problem, the simulation semantics of BS-ESL and discrete-event simulation of RTL SystemC were formalized and provide a solution based on this formalization

Translating an informal design intent into a formal specification is an error prone process. A designer may be able to claim that his implementation meets his formal specification. But, in many cases, he cannot confidently claim that his formal specification correctly captures the original design intent. This problem, in our views, is due to global causal reasoning, as we show with LUSTRE for a Subway system. To resolve this lack of confidence, we briefly present our interactive design tool, which forces a designer to reason locally while formally specifying the design intent.

Type inference and type matching algorithms in the context of a component composition framework are described in this paper. These algorithms facilitate automatic construction of system models from existing SystemC IPs. The approach uses a component composition language to describe an architecture for the system under design and then through automated selection of IPs from an IP library instantiate the architecture. This approach gives rise to many typing problems, and our efficient solutions produce an effective IP-reuse based system modeling and architectural exploration tool that provides productivity gain.

This design presents a system optimized for complex matrix multiplications on the XUP Virtex-II board. Utilizing the GEZEL HW/SW co-simulation environment, the resulting system achieves ~25x speedup over a standard software only implementation. Further system level optimization (with DMA) results in the same coprocessor being speedup by at least another order of magnitude.

This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P ( s ) which indicates the power consumption level given a particular speed. We assume that P ( s ) is convex, nondecreasing, and nonnegative for s ≥ 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.

System level design methodology and language support for high-level modeling enhances productivity for designing complex embedded systems. For an effective methodology, efficiency of simulation and a sound refinement-based implementation path are also necessary. Although some of the recent system level design languages (SLDLs) such as SystemC, SystemVerilog, or SpecC have features for system level abstractions, several essential ingredients are missing from these. We consider: 1) explicit support for multiple models of computation (MoCs) or heterogeneity so that distributed reactive embedded systems with hardware and software components can be easily modeled; 2) the ability to build complex behaviors by hierarchically composing simpler behaviors and the ability to distinguish between structural and heterogeneous behavioral hierarchy; and 3) hierarchical composition of behaviors that belong to distinct MoCs, as essential for successful SLDLs. One important requirement for such an SLDL should be that the simulation semantics are compositional, and hence no flattening of hierarchically composed behaviors are needed for simulation. In this paper, we show how we designed SystemC extensions to facilitates for heterogeneous behavioral hierarchy, compositional simulation semantics, and a simulation kernel that shows up to 40% more efficient than standard SystemC simulation

We present the EWD design environment and methodology, a modeling and simulation framework suited for complex and heterogeneous embedded systems with varying degrees of expressibility and modeling fidelity. This environment promotes the use of multiple models of computation (MoCs) to support heterogeneity and metamodeling for conformance tests of syntactic and static semantics during the process of modeling. Therefore, EWD is a multiple MoC modeling and simulation framework that ensures conformance of the MoC formalisms during model construction using a metamodeling approach. In addition, EWD provides a suite of translation tools that generate executable models for two simulation frameworks to demonstrate its language-independent modeling framework. The EWD methodology uses the Generic Modeling Environment for customization of the MoC-specific modeling syntax into a visual representation. To embed the execution semantics of the MoCs into the models, we have built parsing and translation tools that leverage an XML-based interoperability language. This interoperability language is then translated into executable Standard ML or Haskell models that can also be analyzed by existing simulation frameworks such as SML-Sys or ForSyDe. In summary, EWD is a metamodeling driven multitarget design environment with multi-MoC modeling capability.

It is anticipated that self assembled ultra-dense nanomemories will be more susceptible to manufacturing defects and transient faults than conventional CMOS-based memories, thus the need exists for fault-tolerant memory architectures. The development of such architectures will require intense analysis in terms of achievable performance measures- power dissipation, area, delay and reliability. In this paper, we propose and develop a hybrid automation framework, called HMAN, that aids the design and analysis of fault-tolerant architectures for nanomemories. Our framework can analyze memory architectures at two different levels of the design abstraction, namely the system and circuit levels. To the best of our knowledge, this is the first such attempt at analyzing memory systems at different levels of abstraction and then correlating the different performance measures. We also illustrate the application of our framework to self-assembled crossbar architectures by analyzing a hierarchical fault-tolerant crossbar-based memory architecture that we have developed.

Enhancing productivity for designing complex embedded systems requires system level design methodology and language support for capturing complex design in high level models. For an effective methodology, efficiency of simulation and a sound refinement based implementation path are also necessary. Although some of the recent system level design languages for system level abstractions, several essential ingredients are missing from these. We consider (i) explicit support for multiple models of computation (MoCs) or heterogeneity; (ii) the ability to build complex behaviors by hierarchically composing simpler behaviors; and (iii) hierarchical composition of behaviors that belong to distinct models of computation, as essential for successful SLDLs. These render an SLDL with modeling fidelity that exploits both heterogeneity and hierarchy and allows for simpler modeling and efficient simulation. One important requirement for such an SLDL should be that the simulation semantics be also compositional, and hence no flattening of hierarchically composed behaviors be needed for simulation. In this paper we show how we designed SystemC extensions to provide facilities for heterogeneous behavioral hierarchy, compositional simulation semantics, and implemented a simulation kernel which we show experimentally as up to 50% more efficient than standard SystemC simulation

Most hardware description languages do not enforce determinacy, meaning that they may yield races. Race conditions pose a problem for the implementation, verification, and validation of hardware. Enforcing determinacy at the modeling level provides a solution to this problem. In this paper, we consider a common model of computation for hardware modeling - a network of cycle-true finite-state-machines with datapaths (FSMDs) - and we identify the conditions under which such models are guaranteed to be race-free. We base our analysis on the Kahn principle and a formal framework to represent FSMD semantics. We present our conclusions as four simple and easy to enforce modeling rules. A hardware designer that applies those four modeling rules, will thus obtain race-free hardware

With current CMOS technologies reaching beyond 65 nanometers mark, and the highlights of computing fabrics such as molecular, DNA guided assemblies, quantum comput- ing, carbon nanotube based transistors etc. are bringing the focus onto nanotechnology.The term nano-computing now implies computing with alternative emerging nano-scale technologies as well as with large scale parallelism afforded by the shrinking silicon technologies, with the added burden of rampant defects and faults. The optimization factors and assumptions we made so far in hardware designs become no longer valid for such computing fabrics. The parallelism heretofore unavailable can now be applied, and help us realize newer ways of designing softwares and algorithms. The question therefore to ask is: do we need drastic new approaches to design hardware and software? This panel comprising of experts from formal methods, reliability, spatial computing, hardware/software design will discuss this question from individual perspectives in an attempt to come up with a cogent set of questions researchers need to answer.

Bluespec's rule-based model of computation (MoC) for hardware concurrency has gained attention for several reasons. From its basis in term rewriting systems, rules have the property of atomicity, which improves correctness by construction, particularly in large-scale concurrency with finegrained, dynamic resource sharing (typical in complex hardware). Rule-based interface methods extend atomicity across module boundaries, have a natural transactional reading, and precisely and formally characterize resource-sharing constraints. All this can be synthesized to hardware with competitive quality. SystemC expresses concurrency with threading and events, just like RTL, where it is difficult to deal with fine-grain concurrency and resource sharing. Further, there is no systematic methodology for module composition. Thus, while SystemC is suitable for very coarse modeling and for embedded software development, its limitations make it difficult to model correct by construction hardware systems accurately. In this paper, we show how to integrate Bluespec's rule-based MoC into SystemC. We augment SystemC modules with rules and rule-based interface methods, and augment the SystemC simulation kernel with a rule execution kernel. The integration is augmentative in that a model can contain both rule-based modules (where hardware accuracy is desired) as well as core SystemC or TLM modules (for embedded software, instruction-set simulators, existing SystemC IP, or pure behavioral models), thus providing the advantages of each MoC where appropriate

Synthesis from guarded atomic actions used for high-level descriptions of hardware designs has been shown to be a successful methodology for generating efficient designs (Arvind et al., 2004). This methodology uses CAOS (concurrent action oriented specifications) for hardware description which is based on the idea of term rewriting systems (TRS's) (Baader and Nipkov, 1998; Hoe and Arvind, 1999). A prime example of CAOS is Bluespec where the behavior of a design is described using various guarded atomic actions. Hardware synthesis from such specifications can infer more parallelism than is possible from the traditional methods of behavioral synthesis using CDFGs (control data-flow graphs) (Gupta et al.; Chang and Pedram, 1999; Lakshminarayana et al., 1998). Hardware implementations generated from CAOS can exploit the parallelism germane in the computation and execute maximal set of actions concurrently in order to reduce the latency of the design. The concurrent execution of the actions enhances the performance of the hardware designs in terms of the delay but high power consumption may become an issue when multiple such actions are executed concurrently. Thus, there is a need to reduce power consumption during the CAOS-based synthesis. In this paper, we consider a CAOS similar to Bluespec's model of computation and present two strategies targeting the reduction of peak power and dynamic power in designs generated from such specifications. One strategy uses the re-scheduling of the atomic actions to generate a low-power schedule whereas the other exploits the factorization as well as the re-scheduling of the actions for power reduction

With increasing clock frequencies, the signal delay on some interconnects in a System on Chip (SoC) often exceeds the clock period, which necessitates latency insensitive protocols (LIPs). The correctness of a system composed of synchronous blocks communicating via LIPs is established by showing latency equivalence between a completely synchronous composition of the blocks, and the LIP-based composition. Every time a new LIP is conceived, it needs to be debugged and then proven correct. Mathematical theorems to establish correctness, though elegant, are error prone, and tedious to create for every new variant of LIPs. In this work, we present validation frameworks for families of LIPs, both for dynamic validation, useful for early debug cycles, and formal verification for formal proof of correctness. This can be a useful framework in the hands of designers trying to create new LIPs or to optimize existing ones for design convergence.

Existing system-level design languages (SLDLs) and frameworks mainly provide a modeling and a simulation framework. However, there is an increasing demand for supporting tools to aid designers in quick and faster design space and architectural exploration. As a result, numerous tools such as integrated development environments (IDEs) and others that help in debugging, visualization, validation, and verification are commonly employed by designers. As with most tools, they are targeted for a specific purpose, making it difficult for designers to possess all desired features from one particular tool. Only public-domain tools can be easily extended or interfaced with other existing tools, which a lot of the existing commercial tools do not promote. Having an extendable framework allows designers to implement their own desirable features and incorporate them into their framework. However, for technology reuse and transfer, it is important to have a tidy infrastructure for interfacing the extension with the framework, such that the added solution is not highly coupled with the environment, making distribution and deployment to other frameworks difficult, if not impossible. This requires a plug-and-play framework where features can be easily integrated. These issues of extendibility, deployment, and the inadequacies in SLDLs and frameworks are tackled by presenting a service-oriented architecture for validating SLDs for SystemC, called CARH, We code name our software systems after famous computer scientists. CARH which uses a variety of open-source technologies such as Doxygen, Apache's Xerces extensible markup language parsers, SystemC, and the adaptive communication environment (ACE) object request broker.

With the growing acceptance of SystemC in co-design environments there is a need to further improve the simulation performance of complex designs. Our previous work has shown that simulation performance can be improved by carefully restructuring such designs. As a well known formal model for concurrent systems with a good balance between their expressive power and the theoretical results available for correlating structural properties with behavior, free-choice Petri nets were an ideal candidate for formalizing our restructuring technique. To do so we show how SystemC code can be mapped onto such nets followed by how such a labeled net can be reduced in a semantics preserving way. The end result is a restructured design which, as our experiments show, has improved simulation performance over the original models.

We describe race-free properties of a hardware description language called GEZEL. The language describes networks of cycle-true finite-state-machines with datapaths (FSMDs). We derive a set of four rules under which a network of such FSMDs satisfies the Kahn principle. When applying those rules, GEZEL programs will be determinate and a designer will thus obtain race-free hardware. We define extended FSMD networks as FSMD networks for which some components are user-defined and not specified as FSMDs. An important result is that the determinate properties of the FSMD network are also valid for the extended FSMD network provided that the user-defined components are determinate. Most hardware description languages do not have this determinacy. Their simulation semantics are dependent on simulator implementation, and on a run-time race resolution mechanism. We therefore position GEZEL as a model of computation that RTL designers should have in mind while creating RTL models. In fact, we can generate SystemC and other HDL code from GEZEL models, thereby guaranteeing the determinacy in the generated HDL code.

Abstract Dynamic power management (DPM) refers to the use of runtime strategies in order to achieve a tradeoff between the performance and power consumption of a system and its components. We present an approach to analysing stochastic DPM strategies using probabilistic model checking as the formal framework. This is a novel application of probabilistic model checking to the area of system design. This approach allows us to obtain performance measures of strategies by automated analytical means without expensive simulations. Moreover, one can formally establish various probabilistically quantified properties pertaining to buffer sizes, delays, energy usage etc., for each derived strategy.

Probabilistic-model checking is a formal verification technique for analyzing the reliability and performance of systems exhibiting stochastic behavior. In this paper, we demonstrate the applicability of this approach and, in particular, the probabilistic-model-checking tool PRISM to the evaluation of reliability and redundancy of defect-tolerant systems in the field of computer-aided design. We illustrate the technique with an example due to von Neumann, namely NAND multiplexing. We show how, having constructed a model of a defect-tolerant system incorporating probabilistic assumptions about its defects, it is straightforward to compute a range of reliability measures and investigate how they are affected by slight variations in the behavior of the system. This allows a designer to evaluate, for example, the tradeoff between redundancy and reliability in the design. We also highlight errors in analytically computed reliability bounds, recently published for the same case study.

As SystemC gains popularity as a modeling language of choice for system-on-chip (SoC) designs, heterogeneous modeling in SystemC and efficient simulation become increasingly important. However, in the current reference implementation, all SystemC models are simulated through a nondeterministic discrete-event (DE) simulation kernel that schedules events at run time mimicking other models of computation (MoCs) using DE, which may get cumbersome. This sometimes results in too many delta cycles hindering the simulation performance of the model. SystemC also uses this simulation kernel as the target simulation engine. This makes it difficult to express different MoCs naturally in SystemC. In an SoC model, different components may need to be naturally expressible in different MoCs. These components may be amenable to static scheduling-based simulation or other presimulation optimization techniques. The goal is to create a simulation framework for heterogeneous SystemC models and to gain efficiency and ease of use within the framework of SystemC reference implementation. In this paper, a synchronous data flow (SDF) kernel extension for SystemC is introduced. Experimental results showing improvement in simulation time are also presented.

This special issue is based on innovative ideas presented and discussed during the first ACM/IEEE Conference on Formal Methods and Models for Co-Design (MEMOCODE) held at Mont Saint Michel in France during the summer of 2003. Selected papers from the conference were invited for this special issue together with an open call for papers soliciting novel contributions on the topics of this conference. Rigorous reviews of 12 submissions led to the selection of four papers for this special issue. In this editorial statement, we outline the premise and the context of this special issue, and give a short introduction to the theme under consideration and briefly introduce the papers selected. We also thank the authors who submitted their contributions to this special issue, and all the reviewers without whose dedication and hard work toward ensuring the quality of the selections, editing this special issue would have been impossible.

We present an agile formal methodology named eXtreme Formal Modeling (XFM), based on Extreme Programming (XP) concepts to construct abstract models from natural language specifications of complex systems. In particular, we focus on Prescriptive Formal Models (PFMs) that capture the specification of the system under design in a mathematically precise manner. Such models can be used as golden reference models for formal verification, test generation, coverage monitor generation, etc. This methodology for incrementally building PFMs works by adding user stories expressed as LTL formulae gleaned from the natural language specifications, one by one, into the model. XFM builds the models, retaining correctness with respect to incrementally added properties by regressively model-checking all the LTL properties captured theretofore in the model. We illustrate XFM with a graded set of examples consisting of a traffic light controller and a DLX pipeline. To make the regressive model-checking steps feasible with current model-checking tools, we need to control the model size increments at each subsequent step in the process. We therefore analyze the effects of ordering the LTL properties in XFM on the statespace growth rate of the model. We compare three different property-ordering methodologies: ad hoc ordering, property-based ordering, and predicate-based ordering. We experiment on the models of the ISA bus monitor and the arbitration phase of the Pentium Pro bus. We experimentally show and mathematically reason that the predicate-based ordering is the best among these orderings. Finally, we present a GUI-based toolbox that we implemented to build PFMs using XFM.

Dynamic power management (DPM) refers to the problem of judicious application of various low-power techniques based on runtime conditions in an embedded system to minimize the total energy consumption. To be effective, often such decisions take into account the operating conditions and the system-level design goals. DPM has been a subject of intense research in the past decade driven by the need for low power consumption in modern embedded devices. We present a comprehensive overview of two closely related approaches to designing DPM strategies, namely, competitive analysis approach and model checking approach based on adversarial modeling. Although many other approaches exist for solving the system-level DPM problem, these two approaches are closely related and are based on a common theme. This commonality is in the fact that the underlying model is that of a competition between the system and an adversary. The environment that puts service demands on devices is viewed as an adversary, or to be in competition with the system to make it burn more energy, and the DPM strategy is employed by the system to counter that.

Growing design sizes and shrinking time to market windows can only be met with drastically increased productivity. One way to obtain this is a smart reuse of intellectual property. This paper presents a methodology for modular design with the help of component abstraction. It describes how imperative components can be transformed into a formal, synchronous description to provide behavioral types to the components. The synchronous composition of these abstracted components helps discover errors in the component composition. The presented methodology is illustrated by the detailed case study of a Finite Impulse Response filter. We transform initial \systemc\ modules into an intermediate static single assignment representation which is used as a basis from which corresponding behavioral types are built.

We lay a foundation for modeling and validation of asynchronous designs in a multi-clock synchronous programming model. This allows us to study properties of globally asynchronous systems using synchronous simulation and model-checking toolkits. Our approach can be summarized as automatic transformation of a design consisting of two asynchronously composed synchronous components into a fully synchronous multi-clock model preserving behavioral equivalence. The ultimate goal of this research is to provide the ability to model and build GALS systems in a fully synchronous design framework and deploy it on an asynchronous network preserving all properties of the system proven in the synchronous framework.

It is expected that nano-scale devices and interconnections will introduce unprecedented level of defects, noise and interferences in the substrates. This consideration motivates the search for new architectural paradigms based on redundancy based defect-tolerant designs. However, redundancy is not always a solution to the reliability problem, and often too much or too little redundancy may cause lack of reliability. The key challenge is in determining the granularity at which defect tolerance is designed, and the level of redundancy to achieve optimal reliability. Various forms of redundancy such as NAND multiplexing, Triple Modular Redundancy (TMR), Cascaded Triple Modular Redundancy (CTMR) have been considered in the fault-tolerance literature. Also, redundancy has been applied at different levels of granularity, such as gate level, logic block level, logic function level, unit level etc. The questions we try to answer in this paper is what level of granularity and what redundancy levels result in optimal reliability for specific architectures. In this paper, we extend previous work on evaluating reliability-redundancy trade-offs for NAND multiplexing to granularity vs. redundancy vs. reliability trade-offs for other redundancy mechanisms, and present our automation mechanism using the probabilistic model checking tool PRISM. We illustrate the power of this automation by pointing out certain anomalies of these trade-offs which are counter intuitive and can only be obtained by designers through automation, thereby providing better insight into defect-tolerant design decisions.

As SystemC gains popularity as a modeling language of choice for system-on-chip (SOC) designs, heterogeneous modeling in SystemC and efficient simulation become increasingly important. However, in the current reference implementation, all SystemC models are simulated through a non-deterministic Discrete-Event simulation kernel, which schedules events at run-time. This sometimes results in too many delta cycles hindering the simulation performance of the model. The SystemC language also seems to target this simulation kernel as the target simulation engine. This makes it difficult to express different Models Of Computation naturally in SystemC. In an SOC model, different components may need to be naturally expressible in different Models Of Computations. Some of these components may be amenable to static scheduling based simulation or other pre-simulation optimization techniques. Our goal is to create a simulation framework for heterogeneous SystemC models, to gain efficiency and ease of use within the framework of SystemC reference implementation. In this paper, we focus on Synchronous Data Flow (SDF) models, where the rates of data produced and consumed by a data flow node/block are known a priori. In digital signal processing (DSP) applications where relative sample rates are specified for each DSP component, such models are quite common. Compile time knowledge of these rates allow the use of static scheduling resulting in significant improvement in simulation efficiency. We describe an alternate SystemC kernel that exploits such static scheduling of SDF models. Our experiments show improvement in simulation time over the original models and over the latest efficiency results from [20].

Nano-computing in the form of quantum, molecular and other computing models is proliferating as we scale down to nano-meter fabrication technologies. However, it is expected that nano-scale devices and interconnections will introduce unprecedented level of defects in the substrates and architectural designs need to accommodate the uncertainty inherent at such scales. This consideration motivates the search for new architectural paradigms based on redundancy based defect-tolerant designs. However, redundancy is not always a solution to the reliability problem, and often too much or too little redundancy may cause lack of reliability. The key challenge is in determining the granularity at which defect tolerance is designed, and the level of redundancy to achieve optimal reliability. Also, redundancy has been applied at different levels of granularity, such as gate level, logic block level, logic function level, unit level etc. Analytical probabilistic models to evaluate these levels are error prone and cumbersome, and do not scale well for complex network of gates. We develop different tools and techniques that can evaluate the reliability measures of combinational logic blocks, and can be used to analyze trade-offs between reliability and redundancy for different architectural configurations. In particular, we report two tools, one of which is a Matlab based tool called Nanolab and the other is a probabilistic model checking based tool named Nanoprism. We also illustrate the effectiveness of our reliability analysis tools by pointing out certain anomalies which are counter-intuitive but can be easily discovered by these tools, thereby providing better insight into defect-tolerant design decisions. We foresee that these tools will help furthering research and pedagogical interests in this area, expedite the reliability analysis process and enhance the accuracy of establishing reliability-redundancy trade-off points.

This industrial panel is organized to discuss the views, experiences and opinions of formal methods practitioners frclni desigri automation, hardware and sofhyare industries, in order to understand rlie industrial needs ar7d trends in rising fnmial methods. In particulas we discuss the currertt tlinist or1 application of fnmlal verificntion in software duveekopnient, and what liurdware fomiai verification experiences bring to bear forfim” sofhvare verification.

We consider the type inference problems in a compositional design environment where the components are automatically instantiated from pre-existing C++-based intellectual property (IP) libraries. We present a component integration language based on scripting for design specification. Our focus is architectural aspects in specification that uses aggregation- as opposed to the more commonly used inheritance- for composition of components. Our approach simplifies architectural specification by employing a type inference and type management environment. We show that the type inference problem is NP-complete. We present a heuristic based on code generation and parameterization to solve the type inference for IP selection in our C++-based composition environment. We have implemented the composition and type management in the BALBOA framework. The results show the utility of our approach.

Despite a number of solid advances in simulation and verification techniques over the last twenty years, semiconductor chip designs continue to see large increases in the cost of verification - both in terms of human resources and time. Most of these increases are due to the growing size and complexity of the chip designs. Many of these designs are complete systems in their own right thus enlarging the scope of the verification problem. Formal verification has held out the most promise for reducing the magnitude of the verification task. Indeed, most major microprocessor teams - at IBM, Intel and Motorola - have routinely hosted formal verification experts since the early '90s. ASIC vendors and their tool providers have been closely following these developments into a number of initiatives and new startup companies driven by that very promise of formal verification. Despite these developments, simulation continues to be the final source of signoff - if not confidence - in chip tapeouts. Why is this so? Formal verification is an important technology to be left at the margins of the validation task. Will formal verification eliminate or limit unit level verification and provide the necessary glue for a realistic validation flow? Will the testbenches be replaced by constraints and assertions? Can validation effort be reused? This panel will explore the issues related to building practical validation flows, and the technologies that the designer community can realistically look forward to materializing in their lifetimes.

This paper presents the BALBOA component composition framework for system-level architectural design. It has three parts: a loosely-typed component integration language (CIL); a set of C++ intellectual property (IP) component libraries; and a set of split-level interfaces (SLIs) to link the two. A CIL component interface can be mapped to many different C++ component implementations. A type-inference system maps all weakly-typed CIL interfaces to strongly typed C++ component implementations to produce an executable architectural model. Thus, this amounts to selecting IP implementations according to a set of connection constraints. The SLIs are used to select, adapt, and validate the implementation types. The advantage of using the CIL is that the design description sizes are much smaller because the runtime infrastructure automatically selects the IP and communication implementations. The type inference facilitates changes by automatically propagating them through the design structure. We show that the inference problem is NP complete and we present a heuristic solution to the problem. We bring forth a number of issues related to the automation of reusable IP composition including type- compatibility checking, split-programming, and introspective composition environment, and demonstrate their utility through design examples.

Online dynamic power management (DPM) strategies refer to strategies that attempt to make power-mode-related decisions based on information available at runtime. In making such decisions, these strategies do not depend upon information of future behavior of the system, or any a priori knowledge of the input characteristics. In this paper, we present online strategies, and evaluate them based on a measure called the competitive ratio that enables a quantitative analysis of the performance of online strategies. All earlier approaches (online or predictive) have been limited to systems with two power-saving states (e.g., idle and shutdown). The only earlier approaches that handled multiple power-saving states were based on stochastic optimization. This paper provides a theoretical basis for the analysis of DPM strategies for systems with multiple power-down states, without resorting to such complex approaches. We show how a relatively simple "online learning" scheme can be used to improve the competitive ratio over deterministic strategies using the notion of "probability-based" online DPM strategies. Experimental results show that the algorithm presented here attains the best competitive ratio in comparison with other known predictive DPM algorithms. The other algorithms that come close to matching its performance in power suffer at least an additional 40% wake-up latency on average. Meanwhile, the algorithms that have comparable latency to our methods use at least 25% more power on average.

This paper describes the Balboa component integration environment that is composed of three parts: a script language interpreter, compiled C++ components, and a set of split-level interfaces to link the interpreted domain to the compiled domain. The environment applies the notion of split-level programming to relieve system engineers of software engineering concerns and to let them focus on system architecture. The script language is a Component Integration Language (CIL) because it implements a component model with introspection and loose typing capabilities. Component wrappers use split-level interfaces that implement the composition rules, dynamic type determination and type inference algorithms. Using an interface description language compiler automatically generates the split-level interfaces. The contribution of this work is two fold: an active code generation technique, and a three-layer environment that keeps the C++ components intact for reuse. We present an overview of the environment, demonstrate our approach by building three simulation models for an adaptive memory controller, and comment on code generation ratios.

We present strategies for "online" dynamic power management (DPM) based on the notion of the competitive ratio that allows us to compare the effectiveness of algorithms against an optimal strategy. This paper makes two contributions: it provides a theoretical basis for the analysis of DPM strategies for systems with multiple power down states; and provides a competitive algorithm based on probabilistically generated inputs that improves the competitive ratio over deterministic strategies. Experimental results show that our probability-based DPM strategy improves the efficiency of power management over the deterministic DPM strategy by 25%, bringing the strategy to within 23% of the optimal offline DPM.

Simple and powerful modeling of concurrency and reactivity along with their efficient implementation in the simulation kernel are crucial to the overall usefulness of system level models using the C++-based modeling frameworks. However the concurrency alignment in most modeling frameworks is naturally expressed along hardware units, being supported by the various language constructs, and the system designers express concurrency in their system models by providing threads for some modules/units of the model. Our experimental analysis shows that this concurrency model leads to inefficient simulation performance, and a concurrency alignment along dataflow gives much better simulation performance, but changes the conceptual model of hardware structures. As a result, we propose an algorithmic transformation of designs written in these C++-based environments with concurrency alignment along units/modules. This transformation, provided as a compiler front-end, will re-assign the concurrency along the dataflow, as opposed to threading along concurrent hardware/software modules, keeping the functionality of the model unchanged. Such a front-end transformation strategy will relieve hardware system designers from concerns about software engineering issues such as, threading architecture, and simulation performance, while allowing them to design in the most natural manner whereas, the simulation performance can be enhanced up to almost two times as shown in our experiments.

No abstract available.