IoT botnet attacks are a major concern these days and their detection is an active area of research. Artificial Neural Networks (ANNs) have proven their power and capabilities to detect botnets effectively. However, the process of ANN structure selection and training has been iterative and experimental where one starts with a random number of layers containing an arbitrary number of neurons within them. Experimental results reveal that this work provides massive gains in terms of computational efficiency over the manually selected network structures.

IoT devices are becoming ubiquitous because of the advent of smart cities and vulnerable to a large number of powerful and sophisticated attacks that can potentially paralyze whole cities. There is a need to develop anomaly detection systems that can work on the same principles as the immune system to continuously learn to detect attacks that are not yet discovered. We present a dynamic framework, Celosia, that is inspired by the immune system offering good accuracy and high performance with minimal human intervention. Celosia employs a continuous learning process to detect abnormal behaviors that are yet to be discovered. It also provides a mechanism to manually define normal and anomalous entities to minimize errors. Celosia provides a layered defence and employs several agents performing their dedicated tasks. Experimental results demonstrate the power and capabilities of this framework, making it an ideal candidate for IoT devices.

IoT devices are becoming ubiquitous and the availability of open-source botnets has made it very easy for anyone to attack and manipulate such connected devices and even infect them. These anomalies are getting sophisticated and powerful enough to generate network traffic at terabits per second (Tbps) and cost companies over a billion dollars a year. We present a novel technique, named Dytokinesis, to separate such anomalous entities. Dytokinesis is inspired by the biological Cytokinesis process in which a cell is divided into two. Dytokinesis, on a similar pattern, performs such a division on a dataset with high accuracy and low latency. Dytokinesis works in different phases and makes use of Empirical Data Analysis (EDA) and Gaussian kernel to bisect the dataset into normal and anomalous classes. Experimental results demonstrate that Dytokinesis obtains significantly higher accuracy compared to other state-of-the-art techniques while achieving the best run-time performance.

Hyper-blocks can significantly improve instruction level parallelism on a wide range of super-scalar and VLIW processors. However, most hyper-block construction approaches aim at minimizing the average-case execution time of a program. In real-time embedded systems, minimizing the worst-case execution time (WCET) of a program is the primary goal of an optimizing compiler. We investigate the hyper-block construction problem for a program executed on a clustered VLIW processor such that the WCET of the program is minimized, and propose a novel heuristic approach considering tail duplications. Our approach is underpinned by a novel priority scheme and a precise tail duplication cost model for computing the WCET of a program. We have implemented our approach in Trimaran 4.0, and compared it with the state-of-the-art approach by using a set of 8 benchmark suites. The experimental results show that our approach achieves the maximum WCET improvement of 20.37% and the average WCET improvement of 11.59%, respectively.

Content dissemination, while achieving efficiency and security, is a key challenge in Smart Cities. Existing encryption and key exchange schemes either fail to fulfill the security requirements or incur unaffordable communication, computation, storage and energy overheads. We present a novel approach, Begonia, that provides both efficiency and security when disseminating content to a significantly large number of devices in a smart city context. Begonia makes use of bilinear maps and elliptic-curve cryptography to achieve communication, computation, storage and energy efficiency. This approach completely removes the need for excess communication for key exchange while achieving the desired cryptographic strength. Additionally, it provides dynamic regrouping, joining and isolation capabilities. Experimental results demonstrate huge performance gains when the number of IoT nodes is very large.

Data aggregation in Wireless Sensor Networks (WSNs) can effectively reduce communication overheads and reduce the energy consumption of sensor nodes. A WSN needs to be not only energy efficient but also secure. Various attacks may make data aggregation unsecure. We investigate the reliable and secure end-to-end data aggregation problem considering selective forwarding attacks and modification attacks in homogeneous WSNs, and propose two data aggregation approaches. Our approaches, namely Sign-Share and Sham-Share, use secret sharing and signatures to allow aggregators to aggregate the data without understanding the contents of messages and the base station to verify the aggregated data and retrieve the raw data from the aggregated data. To the best of our knowledge, this is the first lightweight en-routing malicious node detection in concealed data aggregation. We have performed an extensive simulation to compare our approaches and the two state-of-the-art approaches PIP and RCDA-HOMO. The simulation results show that both Sign-Share and Sham-Share consume a reasonable amount of time in processing and aggregating the data. The simulation results show that our first approach achieved an average network lifetime of 102.33% over PIP and average aggregation energy consumption of 74.93%. In addition, it achieved an average aggregation processing time and sensor data processing time of 95.4% and 90.34% over PIP and 98.7% and 92.07% over RCDA-HOMO, respectively, and it achieved an average network delay of 71.95% over PIP. Although RCDA-HOMO is completely a different technique, a comparison was performed to measure the computational overhead.

We investigate the problem of scheduling a set of nonpreemptible tasks with precedence constraints and individual deadlines on heterogeneous NoC-based, DVFS-enabled MPSoCs with discrete frequencies such that the total energy consumption of all the tasks is minimized, and propose two novel approaches. Our approaches consist of a convex nonlinear programming (NLP)-based algorithm for computing the optimal frequencies of all tasks and communication links under the continuous frequency model, an integer linear programming (ILP)- based algorithm and a polynomial-time heuristic for assigning optimal discrete frequencies to all tasks and communication links. Our experimental results show that in terms of total energy consumption, our approach using ILP outperforms two state-of-the-art approaches, ETFGBF and CA-TMES-Search by up to 69.40% and 48.35%, respectively. Moreover, the performance of our approach using the heuristic is very close to that of our approach using ILP.

Modern embedded processors provide hardware support for cache locking, a mechanism used to facilitate the WCET (Worst-Case Execution Time) calculation of a task. We investigate the problem of integrating task scheduling and cache locking for a set of preemptible tasks with individual release times and deadlines on a multi-core processor with two-level caches. We propose a novel integrated approach that schedules the task set and allocates the locked cache contents of each task to the local caches (L1 caches) and the level-two cache (L2 cache). Our approach consists of three major components, the task scheduler, the L1 cache allocator, and the L2 cache allocator. The task scheduler aims at minimizing the number of task preemptions. The L1 cache allocator converts the interference graph of all the tasks scheduled on each core into a DAG by considering the preemptions between tasks and allocates the L1 cache space to each task. The L2 cache allocator converts the interference graph of all the tasks into a DAG by using a k-longest-path-based graph orientation algorithm and allocates the L2 cache space to each task. Both cache allocators significantly improve the cache utilization for all the caches due to the efficient use of the interference graphs of tasks. We have implemented our approach and compared it with the extended version of the preemption tree-based approach and the static analysis approach without cache locking by using a set of benchmarks from the MRTC WCET benchmark suite and SNU real-time benchmarks. Compared to the extended version of the preemption tree-based approach, the maximum WCRT (Worst Case Response Time) improvement of our approach is 15%. Compared to the static analysis approach, the maximum WCRT improvement of our approach is 37%.

Using mobile sinks to collect sensed data in WSNs (Wireless Sensor Network) is an effective technique for significantly improving the network lifetime. We investigate the problem of collecting sensed data using a mobile sink in a WSN with unreachable regions such that the network lifetime is maximized and the total tour length is minimized, and propose a polynomial-time heuristic, an ILP-based (Integer Linear Programming) heuristic and an MINLP-based (Mixed-Integer Non-Linear Programming) algorithm for constructing a shortest path routing forest for the sensor nodes in unreachable regions, two energy-efficient heuristics for partitioning the sensor nodes in reachable regions into disjoint clusters, and an efficient approach to convert the tour construction problem into a TSP (Travelling Salesman Problem). We have performed extensive simulations on 100 instances with 100, 150, 200, 250 and 300 sensor nodes in an urban area and a forest area. The simulation results show that the average lifetime of all the network instances achieved by the polynomial-time heuristic is 74% of that achieved by the ILP-based heuristic and 65% of that obtained by the MINLP-based algorithm, and our tour construction heuristic significantly outperforms the state-of-the-art tour construction heuristic EMPS.

Data aggregation in WSNs (Wireless Sensor Networks) can effectively reduce communication overheads and the energy consumption of sensor nodes. A WSN needs to be not only energy efficient, but also secure. Various attacks may make data aggregation unsecure. We investigate the reliable and secure endto- end data aggregation problem considering selective forwarding attacks and modification attacks in homogeneous cluster-based WSNs, and propose two data aggregation approaches. Our approaches, namely, Sign-Share and Sham-Share, use secret sharing and signatures to allow aggregators to aggregate the data without understanding the contents of messages and the base station to verify the aggregated data and retrieve the raw data from the aggregated data. We have performed extensive simulations to compare our approaches with the two state-of-theart approaches PIP and RCDA-HOMO. The simulation results show both Sign-Share and Sham-Share are faster in processing and aggregating data.

Caches are widely used in embedded systems to bridge the increasing speed gap between processors and off-chip memory. However, caches make it significantly harder to compute the worst-case execution time (WCET) of a task. To alleviate this problem, cache locking has been proposed. We investigate the WCET-aware I-cache locking problem and propose a novel dynamic I-cache locking heuristic approach for reducing the WCET of a task. For a nonnested loop, our approach aims at selecting a minimum set of memory blocks of the loop as locked cache contents by using the min-cut algorithm. For a loop nest, our approach not only aims at selecting a minimum set of memory blocks of the loop nest as locked cache contents but also finds a good loading point for each selected memory block. We propose two algorithms for finding a good loading point for each selected memory block, a polynomial-time heuristic algorithm and an integer linear programming (ILP)-based algorithm, further reducing the WCET of each loop nest. We have implemented our approach and compared it to two state-of-the-art I-cache locking approaches by using a set of benchmarks from the MRTC benchmark suite. The experimental results show that the polynomial-time heuristic algorithm for finding a good loading point for each selected memory block performs almost equally as well as the ILP-based algorithm. Compared to the partial locking approach proposed in Ding et al. [2012], our approach using the heuristic algorithm achieves the average improvements of 33%, 15%, 9%, 3%, 8%, and 11% for the 256B, 512B, 1KB, 4KB, 8KB, and 16KB caches, respectively. Compared to the dynamic locking approach proposed in Puaut [2006], it achieves the average improvements of 9%, 19%, 18%, 5%, 11%, and 16% for the 256B, 512B, 1KB, 4KB, 8KB, and 16KB caches, respectively.

In real-time embedded system design, one major goal is to construct a feasible schedule. Whether a feasible schedule exists depends on the Worst-Case Execution Time (WCET) of each task. Consequently, it is important to minimize the WCET of each task. We investigate the problem of instruction scheduling and register allocation for a program executed on a clustered Very Long Instruction Word (VLIW) processor such that the WCET of the program is minimized, and propose a novel, unified instruction scheduling and register allocation heuristic approach. Our heuristic approach is underpinned by a set of novel techniques, including spanning graph-based WCET-aware live range splitting, WCET-aware dynamic register pressure control, WCET-aware basic block prioritization for performing integrated instruction scheduling and register allocation, and WCET-aware spill code handling. We have implemented our approach in Trimaran 4.0, and compared it with the state-of-the-art approach by using a set of 20 benchmarks. The experimental results show that our approach achieves the maximum WCET improvement of 29.61% and the average WCET improvement of 10.23%, respectively.

Caches have been widely used in modern embedded processors to bridge the increasing speed gap between processors and off-chip memory. In real-time embedded systems, computing the Worst-Case Execution Time (WCET) of a task is essential for the task scheduler to construct a valid schedule for a task set. Unfortunately, caches make it much harder to compute the WCET of a task. Cache locking has been proposed to alleviate the timing unpredictability problem caused by caches. In this article, we investigate the following WCET-aware data-cache locking problem for a single task. Given a task, select a set of variables as locked cache contents such that the WCET of the task is minimized. We propose two dynamic full cache-locking approaches. The first formulates the problem as a global Integer Linear Programming (ILP) problem that simultaneously selects a minimum set of memory blocks of variables as locked cache contents and allocates them to the data cache. The second iteratively constructs a subgraph of the Control Flow Graph (CFG) of the task in which the lengths of all the paths are close to the longest path length, uses an ILP formulation to select a minimum set of memory blocks of variables in the subgraph as locked cache contents, and allocates the selected memory blocks to the data cache. We also propose two novel, efficient data-cache allocation algorithms for the global ILP approach and the iterative ILP approach, respectively. We have implemented both approaches and compared them with two state-of-the-art approaches, the longest path-based dynamic cache-locking approach and the static WCET analysis approach without cache locking by using a set of benchmarks from the Mälardalen WCET benchmark suite, SNU real-time benchmarks, and Powerstone benchmarks. Compared to the static WCET analysis approach, the average WCET improvements of the first approach range between 11.4% and 26.4%. Compared to the longest path--based, dynamic cache-locking approach, the average WCET improvements of the first approach range between 5.0% and 15.4%. The second approach performs slightly better than the first approach.

We investigate the problem of scheduling a set of non-pre-emptive tasks with individual deadlines and conditional precedence constraints on MPSoCs (MultiProcessor System-on-Chips) with shared memory such that the total processor energy consumption of all the tasks in each scenario is minimized under two power models, namely the dynamic power model and the total power model, and propose a unified two-phase approach. The approach consists of an offline task scheduler and an online task scheduler. The offline scheduler uses a novel priority scheme to assign each task to a processor, constructs a global schedule, and uses convex NLP (NonLinear Programming) to compute an optimal speed for each task. The online task scheduler dynamically performs task reallocation and task rescheduling, and reassigns a speed to each task to utilize the slack time generated by individual scenarios. We have compared our approach with two state-of-the-art approaches by using 23 benchmarks. The experimental result show that the average improvement and the maximum improvement of our approach over the approach proposed by Ge et al. are 19.2% and 28.6%, respectively, and the average improvement and the maximum improvement over the approach proposed by Malani et al. are 53.2% and 74.2%, respectively.

We investigate the latency and network lifetime-aware clustering problem for data collection in a WSN (Wireless Sensor Network) with one base station and propose a novel approach. Our approach consists of a polynomial-time heuristic for constructing clusters, a polynomial-time heuristic and an ILP (Integer Linear Programming) algorithm for constructing a routing tree for inter-cluster communication. We have performed extensive simulations on the network instances of 200, 400, 600, 800 and 1000 sensor nodes with uniform and random distributions, and compared our approach with two state-of-the-art approaches, namely MR-LEACH and DSBCV. Our simulation results show that the average network lifetime improvements of our approach using the ILP algorithm for constructing a routing tree over MR-LEACH and DSBCV are 35% and 62%, respectively, and the performance of the heuristic for constructing a routing tree is comparable to that of the ILP algorithm.

We investigate the problem of reducing the number of branch mispredictions for a task such that its WCET (Worst-Case Execution Time) is minimized, and propose a novel branch correlation-based, hybrid branch prediction approach. Our approach consists of a static profile-based branch correlation analyzer and a dynamic branch predictor. The static profile-based branch correlation analyzer uses profiling and data dependency analysis to find precise correlations between branches and identifies all the branches that do not have any impact on the WCET of the task. The dynamic predictor uses the correlation information to make online predictions. We have implemented our approach and compared it with the two state-of-the-art branch prediction approaches by using a set of benchmark suite. The experimental results show that our approach outperforms the two state-of-the-art approaches. The maximum WCET improvement and the average WCET improvement of our approach over the WCET-aware static branch prediction approach are 41.35% and 11.40%, respectively. The maximum WCET improvement and the average WCET improvement of our approach over the global dynamic branch prediction approach are 32.41% and 7.67%, respectively.

Caches have been extensively used to bridge the increasing speed gap between processors and off-chip memory. However, caches make it much harder to compute the WCET (Worst-Case Execution Time) of a program. Cache locking is an effective technique for overcoming the unpredictability problem of caches. We investigate the WCET aware D-cache locking problem for a single task, and propose two dynamic cache locking approaches. The first approach formulates the problem as a global ILP (Integer Linear Programming) problem that simultaneously selects a near-optimal set of variables as the locked cache contents and allocates them to the D-cache. The second one iteratively constructs a subgraph of the CFG of the task where the lengths of all the paths are close to the longest path length, and uses an ILP formulation to select a near-optimal set of variables in the subgraph as the locked cache contents and allocate them to the D-cache. For both approaches, we propose a novel, efficient D-cache allocation algorithm. We have implemented both approaches and compared them with the longest path-based, dynamic cache locking approach proposed in [22] and the static WCET analysis approach without cache locking proposed in [14] by using a set of benchmarks from the Mälardalen WCET benchmark suite, SNU real-time benchmarks and the benchmarks used in [27]. Compared to the static WCET analysis approach, the average WCET improvements of the first approach range between 11.3% and 31.6%, and the average WCET improvements of the second approach range between 12.3% and 32.9%. Compared to the longest path-based, dynamic cache locking approach, the average WCET improvements of the first approach range between 4.7% and 14.3%, and the average WCET improvements of the second approach range between 5.3% and 15.0%.

This paper presents an on-the-fly register allocator which dynamically detects and utilises lifetime holes for clustered VLIW processors. A lifetime hole is an interval in which a variable does not contain a valid value. A register holding a lifetime hole can be allocated to another variable whose live range fits in the lifetime hole, leading to more efficient utilisation of registers. We propose efficient techniques for dynamically utilising lifetime holes and incorporate these techniques into our on-the-fly register allocator. We have simulated our register allocator and a linear scan register allocator without considering lifetime holes by using the MediaBench II benchmark suite. Our simulation results show that our register allocator reduces the number of spills by 12.5%, 11.7%, 12.7%, for three different processor models, respectively.

Caches are widely used in embedded systems to bridge the increasing speed gap between processors and off-chip memory. However, caches make it significantly harder to compute the WCET(Worst Case Execution Time) of a task. To alleviate this problem, cache locking has been proposed. We investigate the I-cache locking problem, and propose a WCET-aware, min-cut based dynamic instruction cache locking approach for reducing the WCET of a single task. We have implemented our approach and compared it with the two state-of-the-art cache locking approaches by using a set of benchmarks from the MRTC benchmark suite. The experimental results show that our approach achieves the average improvements of 41%, 15% and 7% over the partial locking approach for the 256B, 512B and 1KB caches, respectively, and 7%, 18% and 17% over the longest path based dynamic locking approach for the 256B, 512B and 1KB caches, respectively.

We propose a unified approach to the problem of scheduling a set of tasks with individual release times, deadlines and precedence constraints, and allocating the data of each task to the SPM (Scratchpad Memory) on a single processor system. Our approach consists of a task scheduling algorithm and an SPM allocation algorithm. The former constructs a feasible schedule incrementally, aiming to minimize the number of preemptions in the feasible schedule. The latter allocates a portion of the SPM to each task in an efficient way by employing a novel data structure, namely, the preemption graph. We have evaluated our approach and a previous approach by using six task sets. The results show that our approach achieves up to 20.31% on WCRT (Worst-Case Response Time) reduction over the previous approach.

In embedded systems, SPM (scratchpad memory) is an attractive alternative to cache memory due to its lower energy consumption and higher predictability of program execution. This paper studies the problem of placing variables of a program into an SPM such that its WCET (worst-case execution time) is minimized. We propose an efficient dynamic approach that comprises two novel heuristics. The first heuristic iteratively selects a most beneficial variable as an SPM resident candidate based on its impact on the k longest paths of the program. The second heuristic incrementally allocates each SPM resident candidate to the SPM based on graph coloring and acyclic graph orientation. We have evaluated our approach by comparing with an ILP-based approach and a longest-path-based greedy approach using the eight benchmarks selected from Powerstone and Mälardalen WCET Benchmark suites under three different SPM configurations. Our approach achieves up to 21% and 43% improvements in WCET reduction over the ILP-based approach and the greedy approach, respectively.

In WSNs (wireless sensor networks), sensor nodes are typically battery powered. The number of base stations and their locations have significant impacts on the lifetime of a WSN. We study two multiple base station deployment problems. The first problem is to deploy k static base stations in a WSN such that the lifetime of the WSN is maximised. The second problem is to deploy k mobile base stations in a WSN such that the lifetime of the WSN is maximised. We propose a unified heuristic for both problems. In the special case of one static base station, we propose an optimal, polynomial time algorithm. In the special case of one mobile base station, we present an efficient heuristic. We have simulated our optimal algorithm, our heuristics, and the MinDiff-RE heuristic proposed by Azad and Chockalingam. The simulation results show that our heuristic for a single mobile base station prolongs the lifetime of a WSN by 253% on average compared to our optimal algorithm for a single static base station, and our heuristic for multiple mobile base stations performs 40% better than the MinDiff-RE heuristic on average.

Clustering is a well-known technique for improving the scalability of classical VLIW processors. A clustered VLIW processor consists of multiple clusters, each of which has its own register file and functional units. This paper presents a novel phase coupled priority-based heuristic for scheduling a set of instructions in a basic block on a clustered VLIW processor. Our heuristic converts the instruction scheduling problem into the problem of scheduling a set of instructions with a common deadline. The priority of each instruction vi is the lmax(vi)-successor-tree-consistent deadline which is the upper bound on the latest completion time of vi in any feasible schedule for a relaxed problem where the precedence-latency constraints between vi and all its successors, as well as the resource constraints are considered. We have simulated our heuristic, UAS heuristic and Integrated heuristic on the 808 basic blocks taken from the MediaBench II benchmark suite using six processor models. On average, for the six processor models, our heuristic improves 25%, 25%, 33%, 23%, 26%, 27% over UAS heuristic, respectively, and 15%, 16%, 15%, 9%, 20%, 8% over Integrated heuristic, respectively.

We propose the first polynomial-time code selection algorithm for minimising the worst-case execution time of a non-nested loop executed on a fully pipelined processor that uses scratchpad memory to replace the instruction cache. The time complexity of our algorithm is O(m(ne+n2 log n)), where n and e are the number of basic blocks and the number of edges in the control flow graph of the loop, and m is the size of the scratchpad memory. Furthermore, we propose the first dynamic code selection heuristic for minimising the worst-case execution time of a task by using our algorithm for a non-nested loop. Our simulation results show that our heuristic significantly outperforms a previously known heuristic

To exploit the full potential of GPGPUs for general purpose computing, DOACR parallelism abundant in scientific and engineering applications must be harnessed. However, the presence of cross-iteration data dependences in DOACR loops poses an obstacle to execute their computations concurrently using a massive number of fine-grained threads. This work focuses on iterative PDE solvers rich in DOACR parallelism to identify optimization principles and strategies that allow their efficient mapping to GPGPUs. Our main finding is that certain DOACR loops can be accelerated further on GPGPUs if they are algorithmically restructured (by a domain expert) to be more amendable to GPGPU parallelization, judiciously optimized (by the compiler), and carefully tuned by a performance-tuning tool. We substantiate this finding with a case study by presenting a new parallel SSOR method that admits more efficient data-parallel SIMD execution than red-black SOR on GPGPUs. Our solution is obtained non-conventionally, by starting from a K-layer SSOR method and then parallelizing it by applying a non-dependence-preserving scheme consisting of a new domain decomposition technique followed by a generalized loop tiling. Despite its relatively slower convergence, our new method outperforms red-black SOR by making a better balance between data reuse and parallelism and by trading off convergence rate for SIMD parallelism. Our experimental results highlight the importance of synergy between domain experts, compiler optimizations and performance tuning in maximizing the performance of applications, particularly PDE-based DOACR loops, on GPGPUs.

ILP (instruction level parallelism) processors are being increasingly used in embedded systems. In embedded systems, instructions may be subject to timing constraints. An optimising compiler for ILP processors needs to find a feasible schedule for a set of time-constrained instructions. In this paper, we present a fast algorithm for scheduling instructions with precedence-latency constraints, individual integer release times and deadlines on an ILP processor with multiple functional units. The time complexity of our algorithm is O(n2logd)+min{O(de), O(ne)}+min{O(ne), O(n2.376)}, where n is the number of instructions, e is the number of edges in the precedence graph and d is the maximum latency. Our algorithm is guaranteed to find a feasible schedule whenever one exists in the following special cases: 1) one functional unit, arbitrary precedence constraints, latencies in {0,1}, integer release times and deadlines; 2) two identical functional units, arbitrary precedence constraints, latencies of 0, integer release times and deadlines; 3) multiple identical functional units or multiple functional units of different types, monotone interval-ordered graph, integer release times and deadlines; 4) multiple identical functional units, in-forest, equal latencies, integer release times and deadlines. In case 1) our algorithm improves the existing fastest algorithm from O(n2logn)+min{O(ne), O(n2.376)} to min{O(ne), O(n2.376)}. In case 2) our algorithm improves the existing fastest algorithm from O(ne+n2logn) to min{O(ne), O(n2.376)}. In case 3) no polynomial time algorithm for multiple functional units of different types was known before

In a hard real-time system, critical tasks are subject to timing constraints such as release times and deadlines. All timing constraints must be satisfied when tasks are executed. Nevertheless, given a set of tasks, finding a feasible schedule which satisfies all timing constraints is NP-complete even on one processor.In this paper, we study the following special non-pre-emptive two processor scheduling problem: Given a set of UET (Unit Execution Time) tasks with arbitrary precedence constraints, individual real release times and deadlines, find a feasible schedule on two identical processors whenever one exists. The complexity status of this problem has been open for a long time. we propose the first polynomial algorithm for this problem. Our algorithm is underpinned by the key consistency notion: successor-tree-consistency. The time complexity of our algorithm is O(n4), where n is the number of tasks.

A new rank-based distributed deadlock avoidance algorithm for the AND resource request model is presented. Deadlocks are avoided by dynamically maintaining an invariant Con(WFG): For each pair of processes p/sub i/ and p/sub j/, p/sub i/ is allowed to wait for process p/sub j/ iff the rank of p/sub j/ is greater than that of p/sub i/ for the WFG (Wait-For Graph). Our algorithm neither restricts the order of resource requests nor needs a priori information about resource requests nor causes unnecessary abortion of processes. Multidimensional ranks, which are partially ordered and dynamically modified are used to drastically reduce the cost of maintaining Con(WFG). Our simulation results show that the performance of our algorithm is better than that of existing algorithms.

We propose an efficient algorithm for scheduling UET (unit execution time) instructions with deadline constraints on ILP (instruction level parallelism) processors with multiple functional units of different types. The time complexity of our algorithm is O(ne + nd), where n is the number of instructions, e is the number of edges in the precedence graph and d is the maximum latency. Our algorithm is guaranteed to compute a feasible schedule whenever one exists in the following special cases: 1) arbitrary precedence constraints, latencies in {-1, 0} and two functional units; 2) in-forest, equal latencies and multiple functional units; 3) monotone interval graph and multiple functional units. For all above special cases, if no feasible schedule exists, our algorithm will compute a schedule with minimum lateness. In each of the above special cases, no polynomial time algorithm existed before. Moreover by setting all deadlines to a sufficiently large integer, our algorithm will compute a schedule with minimum length in all the above special cases.