Abstract The incorporation of heterogeneous data models into large-scale e-commerce applications incurs various complexities and overheads, such as redundancy of data, maintenance of different data models, and communication among different models for query processing. Graphs have emerged as data modelling techniques for large-scale applications with heterogeneous, schemaless, and relationship-centric data. Models exist for mapping different types of data to a graph; however, the unification of data from heterogeneous source models into a graph model has not received much attention. To address this, we propose a new framework in this study. The proposed framework first transforms data from various source models into graph models individually and then unifies them into a single graph. To justify the applicability of the proposed framework in e-commerce applications, we analyse and compare query performance, scalability, and database size of the unified graph with heterogeneous source data models for a predefined set of queries. We also access some qualitative measures, such as flexibility, completeness, consistency, and maturity for the proposed unified graph. Based on the experimental results, the unified graph outperforms heterogeneous source models for query performance and scalability; however, it falls behind for database size.

Abstract Existing coverage criteria for Unified Modeling Language (UML)‐based system design have used mostly structural constructs and sequential‐behavioural coverage criteria. However, concurrent‐behavioural coverage criteria are not sufficiently explored. The basic path coverage criteria, in UML‐based system design, do not distinguish between non‐interleaving and interleaving execution paths in concurrent activity diagrams. Herein, the main contribution is to present a new set of coverage criteria, based on activity‐interleaving paths for concurrent activity diagrams. For this, first, we modified the definitions of basic path and basic path coverage criterion, and then we defined the interleaving activity path, interleaving activity path coverage, and total activity path coverage criteria. It is observed that the proposed coverage criteria explore most of the concurrency behaviours to uncover concurrency errors. They help to uncover different types of concurrency errors like synchronization, data‐race, and deadlock.

This paper presents an online scheduling methodology for task graphs with communication edges for multiprocessor embedded systems. The proposed methodology is designed for task graphs which are dynamic in nature either due to the presence of conditional paths or due to presence of tasks whose execution times vary. We have assumed homogeneous processors with broadcast and point-to-point communication models and have presented online algorithms for them. We show that this technique adapts better to variation in task graphs at runtime and provides better schedule length compared to a static scheduling methodology. Experimental results indicate up to 21.5 percent average improvement over purely static schedulers. The effects of model parameters like number of processors, memory, and other task graph parameters on performance are investigated in this paper.

In this work, we present a heuristic search technique (Contract Search) which can be automatically adapted for a specified node expansion limitation. We analyze the node expansion properties of best first search and propose a probabilistic model (rank profile) to characterize heuristic search under restricted expansions. We identify the basic properties of the rank profile and establish its relation with the search space configuration. In Contract Search, we use the rank profile model to formulate an optimal strategy to choose level dependent restriction bounds maximizing the probability of obtaining the goal node under the specified contract. Experimental comparison with anytime search techniques like ARA* and beam search shows that Contract Search outperforms these techniques over a range of constraint specifications.

In this article, we present a heuristic search technique (Contract Search) that can be adapted automatically for a specific node contract. We analyze the node expansion characteristics of best‐first search techniques and identify a probabilistic model (rank profiles) that characterizes the search under restricted expansions. We use the model to formulate an optimal strategy to choose level dependent restriction bounds, maximizing the probability of obtaining the optimal cost goal node under the specified contract. We analyze the basic properties of the rank profiles and establish its relation with the search space configuration and heuristic error distributions. We suggest an approximation scheme for the profile function for unknown search spaces. We show how the basic framework can be adapted to achieve different objectives (like optimizing the expected quality) considering multiple goals and approximate solutions. Experimental comparison with anytime search techniques like ARA* and beam search on a number of search problems shows that Contract Search outperforms these techniques over a range of contract specifications.

Overheating of computer chips leads to degradation of performance and reliability. Therefore, preventing chips from overheating in spite of increased performance requirements has emerged as a major challenge. Since the cost of cooling has been rising steadily, various architecture and application design techniques are used to prevent chip overheating. Temperature-aware task scheduling has emerged as an important application design methodology for addressing this problem in multiprocessor SoC systems. In this work we present the formulation and implementation of a method for analyzing the thermal (chip heating) behavior of a MPSoC task schedule, during the early stages of the design. We highlight the challenges in developing such a framework and propose solutions for tackling them. Due to nondeterminism in task execution times and decision branches, multiprocessor applications cannot be evaluated accurately by the current state-of-the-art thermal simulation and steady-state analysis methods. Hence an analysis covering nondeterministic execution behaviors is required for thermal analysis of MPSoC task schedules. To address this issue we propose a model checking-based approach for solving the thermal analysis problem and formulate it as a hybrid automata reachability verification problem. We present an algorithm for constructing this hybrid automata given the task schedule, a set of power profiles of tasks, and the Compact Thermal Model (CTM) of the chip. Information about task power consumption is inferred from Markov chains which are learned from power profiles of tasks, obtained from simulation or emulation runs. A numerical analysis-based algorithm which uses CounterExample-Guided Abstraction Refinement (CEGAR) is developed for reachability analysis of this hybrid automata. We propose a directed simulation methodology which uses results of a time-bounded analysis of the hybrid automata modeling thermal behavior of the application, to simulate the expected worst-case execution runs of the same. The algorithms presented in this work have been implemented in a prototype tool called HeatCheck . We present experimental results and analysis of thermal behavior of a set of task schedules executing on a MPSoC system.

This work presents a static timing-analysis method for verification of scenario-based real-time properties, on graphical task-level models of embedded applications. Scenario-based properties specify timing constraints which must be honored for specific control-flow behaviors and task execution orderings. Static checking of scenario-based properties currently requires computationally expensive model checking methods. Hence the proposed graph-based static timing-analysis algorithm improves upon the state-of-the-art. This is manifested in a significant performance advantage over timed model checking (up to 1000X in several cases), which suffers from state space explosion. The proposed algorithm also employs compositional reasoning and abstraction refinement for handling large problems. We also illustrate methods for using scenario-based timing analysis, which can act as alternatives to traditional timed model checking for verification of timed systems like FDDI and Fischer protocols. We implement this timing verification algorithm as a tool called SymTime and present experimental results for SymTime comparing it with SPIN, UPPAAL, and a TCTL model checker for Time Petri Nets, called Romeo.

Most of the work done in the field of code compression pertains to processors with fixed-length instruction encoding. The design of a code-compression scheme for variable-length instruction encodings poses newer design challenges. In this work, we first investigate the scope for code compression on variable-length instruction-set processors whose encodings are already optimized to a certain extent with respect to their usage. For such ISAs instruction boundaries are not known prior to decoding. Another challenging task of designing a code-compression scheme for such ISAs is designing the decompression hardware, which must decompress code postcache so that we gain in performance. We present two dictionary-based code compression schemes. The first algorithm uses a bit-vector; the second one uses reserved instructions to identify code words. We design additional logic for each of the schemes to decompress the code on-the-fly. We test the two algorithms with a variable-length RISC processor. We provide a detailed experimental analysis of the empirical results obtained by extensive simulation-based design space exploration for this system. The optimized decompressor can now execute compressed program faster than the native program. The experiments demonstrate reduction in code size (up to 30%), speed-up (up to 15%), and bus-switching activity (up to 20%). We also implement one decompressor in a hardware description language and synthesize it to illustrate the small overheads associated with the proposed approach.

We propose a specification logic called Temporally Attributed Boolean (TAB) Logic for Assertion Based Verification, which allows us to: (i) represent assertions succinctly, (ii) incorporate data-orientation and (iii) associate timing to design intentions. TAB Logic allows us to write specifications functionally linking system variables from different temporal contexts. We present examples to show the motivation for this logic especially in the context of high level modeling of complex real time systems. We formally define TAB Logic, formulate the problem of verification on a simulation trace and present efficient algorithms to check TAB assertions, both offline and online. We present results of application of TAB Logic for Instruction Semantics and Bus Transaction Verification of a bus integrated pipelined processor core implementation. We also employ TAB Logic to validate the Interrupt mode behavior of the processor core implementation. Further, we show the utility of TAB Logic in fault detection. Finally, we demonstrate the applicability of TAB Logic in the domain of simulation based verification of analog circuits like Operational Amplifiers and DC-DC Converters. We finally discuss the limitations of TAB logic and conclude.

This paper presents a hybrid scheduling methodology for task graphs to multiprocessor embedded systems. The proposed methodology is designed for task graphs that are dynamic in nature due to the presence of conditional tasks and tasks whose execution times are unpredictable but bounded. We have presented the methodology as a three-phase strategy, in which task nodes are mapped to the processors in the first (static mapping) phase. In the second (selective duplication) phase, some critical nodes are identified and duplicated for possible rescheduling at runtime, depending on the code memory constraints of the processors. The third (online) phase is a runtime scheduling algorithm that performs list scheduling based on the actual dynamics of the schedule up to the current time. We show that this technique provides better schedule length (up to 20 percent) compared to previous techniques, which are predominantly static in nature, with low overhead and a complexity comparable with existing online techniques. The effects of model parameters like the number of processors, memory, and various task graph parameters on performance are investigated in this paper.

Network topology design problems find application in several real life scenarios. However, most designs in the past either optimize for a single criterion like delay or assume simplistic traffic models like Poisson. Such assumptions make the solutions inapplicable in the practical world. In this paper, we formulate and solve a multiobjective network topology design problem for a realistic Internet traffic model which is assumed to be self similar. We optimize for the average packet delivery delay and network layout cost to construct realistic network topologies. We present a multiobjective evolutionary algorithm (MOEA) to obtain the diverse near-optimal network topologies. For fair comparison, we design a multiobjective deterministic heuristic based on branch exchange – we call the heuristic Pareto Branch Exchange (PBE). We empirically show that the MOEA used performs well for real networks of various sizes, and generated topologies are quite different with significantly larger delays for the self similar traffic model.

In this paper, we consider a biobjective minimum spanning tree problem (MOST) and minimize two objectives - tree cost and diameter - in terms of Pareto-optimality. We assess the quality of obtained MOEA solutions in comparison to well-known diameter-constrained minimum spanning tree (dc-MST) algorithms and further improve MOEA solutions using problem-specific knowledge.

We address the problem of optimizing the quality-time tradeoff of very large scale integration (VLSI) computer-aided design (CAD) algorithms working under various constrained environments. We present a unified meta-reasoning framework to automatically control the progress of iteratively improving CAD algorithms. The control framework uses profile knowledge about the quality-time relation of the algorithms used and generates a combined strategy for time allocation and parameter control that optimizes the expected tradeoff. We present specific formulations for handling single and multiple problems (both dependent and independent) under various constraints. We use the proposed strategies for adjusting the control parameters of standard simulated annealing and genetic algorithm based techniques used in VLSI optimization along with an appropriate time allocation suited for different constraint specifications. Application on several classical problems in the VLSI domain shows that significant improvement in quality-time tradeoff can be achieved.

With the advent of multiprocessor embedded platforms, application partitioning and mapping have gained primacy as a design step. The output of this design step is a multithreaded partitioned application where each thread is mapped to a processing element (processor or ASIC) in the multiprocessor platform. This partitioned application must be verified to be consistent with the native unpartitioned application. This verification task is called application (or task) partitioning verification. This work proposes a code-block-level containment-checking -based methodology for application partitioning verification. We use a UML-based code-block-level modeling language which is rich enough to model most designs. We formulate the application partitioning verification problem as a special case of the containment checking problem, which we call the complete containment checking problem . We propose a state space reduction technique specific to the containment checking, reachability analysis, and deadlock detection problems. We propose novel data structures and token propagation methodologies which enhance the efficiency of containment checking. We present an efficient containment checking algorithm for the application partitioning verification problem. We develop a containment checking tool called TraceMatch and present experimental results. We present a comparison of the state space reduction achieved by TraceMatch with that achieved by formal analysis and verification tools like Spin, PEP, PROD, and LoLA.

The UML activity diagram language is the de facto language for behavioral modeling capable of block level modeling of real time multiprocessor SoC applications where timing behavior is a critical aspect. Although there are several tools for timing verification of logics with branching time semantics, there are no known model checkers for timing verification of logics with linear time semantics as needed for many verification tasks. This work deals with timing verification of UML activity diagram models of applications. We propose a subset of TPTL (timed prepositional temporal logic) for specifying timing queries. We develop an automata based model checker for verifying such queries. We present a comparison of the proposed timing verification with the state of the art for random test-cases.

Wire routing in a VLSI chip often requires minimization of ire-length as well as the number of intersections among multiple nets. Such an optimization problem is computationally hard for which no efficient algorithm or good heuristic is known to exist. Additionally, in a biobjective setting, the major challenge to solve a problem is to obtain representative diverse solutions across the (near-) Pareto-front.In this work, we consider the problem of constructing spanning trees of two geometric graphs corresponding to two nets, each with multiple terminals, with a goal to minimize the total edge cost and the number of intersections among the edges of the two trees. We first design simple heuristics to obtain the extreme points in the solution space, which however, could not produce diverse solutions. Search algorithms based on evolutionary multiobjective optimization (EMO) are then proposed to obtain diverse solutions in the feasible solution space. Each element of this solution set is a tuple of two spanning trees corresponding to the given geometric graphs. Empirical evidence shows that the proposed evolutionary algorithms cover a larger range and are much superior to the heuristics.

All known real-time proportional fair scheduling mechanisms either have high scheduling overheads (O(lg n) per time-slot) or do not efficiently handle dynamic task sets. This paper presents frame-based proportional round-robin (FBPRR), a real-time fair scheduler providing high and bounded proportional fairness accuracy and O(1) scheduling overhead with the ability to efficiently handle a set of dynamic tasks. FBPRR achieves this by applying the benefits of virtual-time round-robin (VTRR) scheduling mechanism within a frame-based scheduling approach. Simulation results show that the algorithm gains a speedup of 5 to 20 times (over O(lg n) complexity schedulers) with fairly high fairness

Microprocessor pipeline simulation at the system level is an extremely important activity in the architecture exploration process. In this article, we address the problem of validating and debugging a pipeline simulator from the specific perspective of instruction scheduling. We propose a general framework for a systematic validation process and show that the assumptions made are justified for most standard pipeline models. The framework does not need any formal specification of the pipeline logic and hence can be readily integrated into the simulation and iteration-based architectural design space exploration process. We propose a concept of semantic equivalence between two simulations called D* equivalence which effectively captures the dataflow between instructions through registers. We then proceed to propose an algorithm which decides this equivalence in time polynomial in the number of instructions executed and the number of registers. We implement the algorithm and demonstrate how the framework facilitates debugging.

We propose a new dynamic slicing technique for object-oriented programs that is more efficient than the related algorithms. We use an extended system dependence graph (ESDG) as the intermediate program representation. Our dynamic slicing algorithm is based on marking and unmarking the edges in the ESDG as and when dependencies arise and cease during runtime.