Task offloading management in 6G vehicular net-works is crucial for maintaining network efficiency, particularly as vehicles generate substantial data. Integrating secure communication through authentication introduces additional computational and communication overhead, significantly impacting offloading efficiency and latency. This paper presents a unified framework incorporating lightweight Identity-Based Cryptographic (IBC) authentication into task offloading within cloud-based 6G Vehicular Twin Networks (VTNs). Utilizing Proximal Policy Optimization (PPO) in Deep Reinforcement Learning (DRL), our approach optimizes authenticated offloading decisions to minimize latency and enhance resource allocation. Performance evaluation under varying network sizes, task sizes, and data rates reveals that IBC authentication can reduce offloading efficiency by up to 50 % due to the added overhead. Besides, increasing network size and task size can further reduce offloading efficiency by up to 91.7%. As a countermeasure, increasing the transmission data rate can improve the offloading performance by as much as 63%, even in the presence of authentication overhead. The code for the simulations and experiments detailed in this paper is available on GitHub for further reference and reproducibility [1].

We consider a block fading wiretap channel, where a transmitter attempts to send messages securely to a receiver in the presence of a hybrid half-duplex adversary, which arbitrarily decides to either jam or eavesdrop the transmitter-to-receiver channel. We provide bounds to the secrecy capacity for various possibilities on receiver feedback and show special cases where the bounds are tight. We show that, without any feedback from the receiver, the secrecy capacity is zero if the transmitter-to-adversary channel stochastically dominates the effective transmitter-to-receiver channel. However, the secrecy capacity is nonzero even when the receiver is allowed to feed back only one bit at the end of each block. Our novel achievable strategy improves the rates proposed in the literature for the nonhybrid adversarial model. We also analyze the effect of multiple adversaries and delay constraints on the secrecy capacity. We show that our novel time sharing approach leads to positive secrecy rates even under strict delay constraints.

We consider the wiretap channel model under the presence of a hybrid, half duplex adversary that is capable of either jamming or eavesdropping at a given time. We analyzed the achievable rates under a variety of scenarios involving different methods for obtaining transmitter CSI. Each method provides a different grade of information, not only to the transmitter on the main channel, but also to the adversary on all channels. Our analysis shows that main CSI is more valuable for the adversary than the jamming CSI in delay-limited scenarios. Similarly, in certain cases under the ergodic scenario, interestingly, no CSI may lead to higher achievable secrecy rates than with CSI.

Network control and management techniques (e.g., dynamic path switching, on-demand bandwidth provisioning) rely on active measurements of end-to-end network status. These measurements are needed to meet network monitoring objectives such as: (a) intra-domain/inter-domain paths statuschecking, (b) network weather forecasting, (c) anomaly event detection and (d) fault-diagnosis. In this paper, we present a novel semantic scheduling algorithm based on deterministic and heuristic scheduling principles to handle measurement request loads for meeting network monitoring objectives that aid in resource adaptation decisions. The semantic priorities specified to our scheduling algorithm that are based on user-level and resource-level policies allow preferential treatment of measurement requests that supercede typical scheduling priorities based on periodicity and execution time. We evaluate our semantic scheduling algorithm using metrics such as cycle time and satisfaction ratio for increasing measurement request loads. Our semantic scheduling algorithm and evaluation study findings are vital to deploy and manage large-scale measurement infrastructures used for meeting monitoring objectives in support of nextgeneration applications and networks.

The computation of an electromagnetic reflectivity image from a set of radar returns is a computationally intensive process. Therefore, the use of high performance computing is required to form images from radar signals in a short time frame. This paper explores the use of distributed memory cluster computers and accelerator technologies such as GPUs for radar signal analysis applications, particularly backprojection image formation. We obtain good results with the use of GPUs and compare their performance in terms of execution time with distributed memory cluster computers. When using a configuration with 4 GPU-accelerated nodes, we achieve speedups up to 3.45x for different input and output data size combinations.

In this paper, we propose a static (compile-time) scheduling extension that considers reconfiguration and task execution together when scheduling tasks on reconfigurable hardware, designated as Mutually Exclusive Groups (-MEG), that can be used to extend any static list scheduler. In simulation, using -MEG generates higher quality schedules than those generated by the hardware-software co-scheduler proposed by Mei, et al. and using a single configuration with the base scheduler. Additionally, we propose a dynamic (run-time), fault tolerant scheduler targeted to reconfigurable hardware. We present promising preliminary results using the proposed fault-tolerant dynamic scheduler, showing that application performance gracefully degrades when shrinking the available processing resources.

Many DAG scheduling algorithms generate schedules that require prohibitively large number of processors. To address this problem, we propose a generic algorithm, SC, to minimize the processor requirement of any given valid schedule. SC preserves the schedule length of the original schedule and reduces processor count by merging processor schedules and removing redundant duplicate tasks. To the best of our knowledge, this is the first algorithm to address this highly unexplored aspect of DAG scheduling. On average, SC reduced the processor requirement 91, 82, and 72 percent for schedules generated by PLW, TCSD, and CPFD algorithms, respectively. SC algorithm has a low complexity (O(\vert {\cal N}\vert^3)) compared to most duplication-based algorithms. Moreover, it decouples processor economization from schedule length minimization problem. To take advantage of these features of SC, we also propose a scheduling algorithm SDS, having the same time complexity as SC. Our experiments demonstrate that schedules generated by SDS are only 3 percent longer than CPFD (O(\vert {\cal N}\vert^4)), one of the best algorithms in that respect. SDS and SC together form a two-stage scheduling algorithm that produces schedules with high quality and low processor requirement, and has lower complexity than the comparable algorithms that produce similar high-quality results.

Abstract Emerging Wireless Sensor Network (WSN) applications demand considerable computation capacity for in‐network processing in resource limited WSN environments. To achieve the required processing capacity under energy consumption constraints, collaboration among sensors through parallel processing methods emerges as a promising solution. Although such methods have been extensively studied in wired networks of processors, its counterpart for WSNs remains largely unexplored. In this paper, a localized task mapping and scheduling solution for energy‐constrained applications in WSNs, Energy‐constrained Task Mapping and Scheduling (EcoMapS), is presented. EcoMapS guarantees energy consumption constraints while minimizing schedule length. EcoMapS incorporates channel modeling, concurrent task mapping, communication and computation scheduling, and sensor failure handling algorithms. Simulation results show significant performance improvements of EcoMapS over existing mechanisms in terms of minimizing schedule lengths subject to energy consumption constrains. Copyright © 2007 John Wiley & Sons, Ltd.

This paper presents a middleware framework for storing, accessing and analyzing massive-scale semantic graphs. The framework, MSSG, targets scale-free semantic graphs with O(1012) (trillion) vertices and edges. Here, we present the overall architectural design of the framework, as well as a prototype implementation for cluster architectures. The sheer size of these massive-scale semantic graphs prohibits storing the entire graph in memory even on medium- to large-scale parallel architectures. We therefore propose a new graph database, grDB, for the efficient storage and retrieval of large scale-free semantic graphs on secondary storage. This new database supports the efficient and scalable execution of parallel out-of-core graph algorithms which are essential for analyzing semantic graphs of massive size. We have also developed a parallel out-of-core breadth-first search algorithm for performance study. To the best of our knowledge, it is the first of such algorithms reported in the literature. Experimental evaluations on large real-world semantic graphs show that the MSSG framework scales well, and grDB outperforms widely used open-source out-of-core databases, such as BerkeleyDB and MySQL, in the storage and retrieval of scale-free graphs

In this paper, a fully Ad-Hoc Multi-hop Broadcast protocol (AMB) is proposed for inter-vehicular networks. The AMB is an ad-hoc extension of the UMB protocol which handles broadcast in intersections with the help of repeaters. The AMB protocol eliminates the most important drawback - infrastructure dependence - of the UMB protocol by employing an efficient intersection broadcast mechanism. When there is an intersection in the path of the message dissemination, new directional broadcasts to all road segments are initiated by the vehicle closest to the intersection with a fully ad-hoc algorithm without apriori topology information. The simulation results confirm that our protocol has a very high success rate and efficient channel utilization. Consequently, it is concluded that there is no need for infrastructure support unless the the line-of-sight among different road segments incident to an intersection is blocked with obstacles.

We propose a new duplication-based DAG scheduling algorithm for heterogeneous computing environments. Contrary to the traditional approaches, proposed algorithm traverses the DAG in a bottom-up fashion while taking advantage of task duplication and task insertion. Experimental results on random DAGs and three different application DAGs show that the makespans generated by the proposed DBUS algorithm are much better than those generated by the existing algorithms, HEFT, HCPFD and HCNF.

With the increasing importance of energy consumption considerations and new requirements of emerging applications, in-network processing of information gains recognition as a viable solution for wireless sensor networks (WSNs). The required processing capability can be achieved through locally collaborative information processing among sensors. Task mapping and scheduling plays an important role in efficient collaborative information processing. Although task mapping and scheduling in wired networks of processors has been well studied in the past, its counterpart for WSNs remains largely unexplored. In this paper, a task mapping and scheduling solution for real-time applications in WSNs, real-time task mapping and scheduling (RT-MapS), is presented. RT-MapS incorporates wireless channel modeling, hyper-DAG extension, concurrent task mapping, communication and computation scheduling, and dynamic voltage scaling (DVS) methods. Simulation results show significant performance improvements compared with existing mechanisms in terms of providing deadline guarantee with minimum energy consumption

The static staging heuristics proposed in the literature for staging the data items associated with real-time distributed applications adhere to a method by which only one data item is transferred in each communication step to optimize a specific cost function. In this paper, we first propose the Extended Partial Path (EPP) algorithm based on the same method. In terms of maximizing the number of satisfied requests, we have analytically shown that EPP has a performance that is equal to or greater than the Partial Path Heuristic (PPH) introduced previously [CHECK END OF SENTENCE], thanks to excluding the data items that cannot be satisfied by PPH from scheduling and scheduling the satisfiable data-items along their extended paths. In contrast to EPP and other data staging heuristics proposed, we develop the concurrent scheduling (CS) heuristic which allows simultaneous transfer of more than one data item in an organized fashion, thereby improving the overall performance of the staging system. At the heart of the CS heuristic are EPP and the local priority assignment method devised for solving the conflicts between data items at the intermediate nodes. The extensive simulation results further confirm the superiority of the CS heuristic over PPH.

We propose a novel replication-based two-phase scheduling algorithm designed to achieve DAG scheduling with small makespans and high efficiency. In the first phase, the schedule length of the application is minimized using a novel approach that utilizes partial schedules. In the second phase, the number of processors required is minimized by eliminating and merging these partial schedules. Experimental results on random DAGs show that the makespans generated by the proposed algorithm are slightly better than those generated by the well known CPFD algorithm whereas the number of processors used is less than half of what is needed by CPFD solutions.

Collaboration among sensors through parallel processing mechanisms emerges as a promising solution to achieve high processing power in resource-restricted wireless sensor networks (WSN). Although task mapping and scheduling in wired networks of processors has been well studied in the past, their application to WSNs remains largely unexplored. Due to the limitations of WSNs, existing algorithms cannot be directly implemented in WSNs. In this paper, a task mapping and scheduling solution for energy-constrained applications in WSNs, energy-constrained task mapping and scheduling (EcoMapS), is presented. EcoMapS incorporates channel modeling, concurrent task mapping, communication and computation scheduling, and sensor failure handling algorithm. The performance of EcoMapS is evaluated through simulations with randomly generated directed acyclic graphs (DAG). Simulation results show significant performance improvements compared with an existing mechanism in terms of minimizing schedule lengths subject to energy consumption constrains

In recent studies, using mobile elements (MEs) as mechanical carriers of data has been shown to be an effective way of prolonging sensor network life time and relaying information in partitioned networks. As the data generation rates of sensors may vary, some sensors need to be visited more frequently than others. In this paper, a partitioning-based algorithm is presented that schedules the movements of MEs in a sensor network such that there is no data loss due to buffer overflow. Simulation results show that the proposed Partitioning Based Scheduling (PBS) algorithm performs well in terms of reducing the minimum required ME speed to prevent data loss, providing high predictability in inter-visit durations, and minimizing the data loss rate for the cases when the ME is constrained to move slower than the minimum required ME speed.

A heterogeneous computing (HC) system is composed of a suite of geographically distributed high-performance machines interconnected by a high-speed network, thereby providing high-speed execution of computationally intensive applications with diverse demands. In HC systems, however, there is a possibility of machine and network failures and this can have an adverse impact on applications running on the system. In order to decrease the impact of failures on an application, matching and scheduling algorithms must be devised which minimize not only the execution time but also the failure probability of the application. However, because of the conflicting requirements, it is not possible to minimize both at the same time. Thus, the goal of this paper is to develop matching and scheduling algorithms which account for both the execution time and the failure probability and can trade off execution time against the failure probability of the application. In order to attain these goals, a biobjective scheduling problem is first formulated and then two different algorithms, the biobjective dynamic level scheduling algorithm and the biobjective genetic algorithm, are developed. Unique to both algorithms is the expression used for computing the failure probability of an application with precedence constraints. The simulation results confirm that the proposed algorithms can be used for producing task assignments where the execution time is weighed against the failure probability.

Large-scale data intensive applications with real-time requirements are currently emerging in many disciplines of science and engineering. Such applications can benefit from a grid environment provided that an efficient solution to the following data scheduling problem can be found: schedule the transfer of a set of large-scale data objects of distributed applications in a grid environment so as to meet real-time constraints associated with these data transfers. Based on this premise, This work focuses on the aforementioned problem and proposes a new effective path-selection based scheduling algorithm. The algorithm performs its optimization based on a schedule reflection model; a new cost criterion that takes into account the satisfiability of each application as a whole. We show, by simulation, that our algorithm improves the performance of data intensive real-time applications.

Summary form only given. The problem of scheduling a set of independent tasks (a metatask) with multiple QoS needs, such as timeliness, reliability, versions, security and priority, in a heterogeneous computing (HC) environment is referred to as the QoS-based scheduling problem. Several heuristics have been proposed in the literature to solve the QoS-based scheduling problem, which is proven to be NP-hard. Selecting the best heuristic to use in a given HC environment is not trivial, since each heuristic makes different assumptions about the underlying QoS model. This article performs a comparative study of five such heuristics, namely QSMTS-IP, min-min, genetic algorithm, least slack first and sufferage. The heuristics have been modified from their original implementations to incorporate additional QoS attributes, the notion of service-types and to enable them to be simulated using a common set of assumptions. The study provides a fair basis for comparison of these heuristics, for tasks with varied service-types (hard, soft or best-effort) for each QoS dimension and varied degrees of tightness of task deadlines. The heuristics are outlined, the QoS-model is defined and the simulation environment is described. The simulation study shows how each heuristic performs in terms of number of satisfied users, makespan and total utility. The results provide suggestions on which heuristic is best suited for conditions prevailing in a particular HC environment.

We present a strongly fault-tolerant design for the k-ary n-cube multiprocessor and examine its reconfigurability. Our design augments the k-ary n-cube with (k/j)/sup n/ spare nodes. Each set of j/sup n/ regular nodes is connected to a spare node and the spare nodes are interconnected as either a (k/j)-ary n-cube if j/spl ne/(k/2) or a hypercube of dimension n if j=k/2. Our approach utilizes the capabilities of the wave-switching communication modules of the spare nodes to tolerate a large number of faulty nodes. Both theoretical and experimental results are examined. Compared with other proposed schemes, our approach can tolerate significantly more faulty nodes with a low overhead and no performance degradation.

Finding an optimal solution to the problem of scheduling an application modeled by a directed acyclic graph (DAG) onto a set of heterogeneous machines is known to be an NP-hard problem. In this study, we present a duplication based scheduling algorithm, namely the levelized duplication based scheduling (LDBS) algorithm, which solves this problem efficiently. The primary goal of LDBS is to minimize the schedule length of applications. LDBS can accommodate different duplication heuristics, thanks to its modular design. Specifically, we have designed two different duplication heuristics with different time complexities. The simulation studies confirm that LDBS is a very competitive scheduling algorithm in terms of minimizing the schedule length of applications.

Providing quality of service (QoS) to high bandwidth video, voice and data applications in wireless networks is an important problem. Such applications are in the class of real-time applications; they need communication operations to complete within certain targeted deadlines. Based on this premise, this paper addresses the design of distributed MAC layer protocols that incorporate explicit support for real-time traffic in an ad-hoc wireless network. Specifically, we have developed two new MAC layer protocols, namely the elimination by sieving (ES-DCF) and the deadline bursting (DB-DCF) protocols. Both algorithms use deterministic collision resolution algorithms in order to provide timely delivery guarantees to different classes of real-time traffic. The extensive simulation studies conducted confirmed that ES-DCF and DB-DCF perform well for hard-real-time traffic and soft-real-time traffic, respectively.

In a heterogeneous distributed computing system, machine and network failures are inevitable and can have an adverse effect on applications executing on the system. To reduce the effect of failures on an application executing on a failure-prone system, matching and scheduling algorithms which minimize not only the execution time but also the probability of failure of the application must be devised. However, because of the conflicting requirements, it is not possible to minimize both of the objectives at the same time. Thus, the goal of this paper is to develop matching and scheduling algorithms which account for both the execution time and the reliability of the application. This goal is achieved by modifying an existing matching and scheduling algorithm. The reliability of resources is taken into account using an incremental cost function proposed in this paper and the new algorithm is referred to as the reliable dynamic level scheduling algorithm. The incremental cost function can be defined based on one of the three cost functions developed here. These cost functions are unique in the sense that they are not restricted to tree-based networks and a specific matching and scheduling algorithm. The simulation results confirm that the proposed incremental cost function can be incorporated into matching and scheduling algorithms to produce schedules where the effect of failures of machines and network resources on the execution of the application is reduced and the execution time of the application is minimized as well.

This paper describes a senior/graduate level course in hardware logic verification being offered by The Ohio State University in cooperation with IBM. The need for the course is established through the growing importance of logic verification to users of custom logic designs. We discuss the short-term and long-term goals for the course, and describe the course content and format. The course relies heavily on lab projects to illustrate the main concepts. Three projects and a final project review are described.

This paper investigates the problem of matching and scheduling of an application, which is composed of tasks with precedence constraints, to minimize both execution time and probability of failure of the application in a heterogeneous computing system. In general, however, it is impossible to satisfy both objectives at the same time because of conflicting requirements. The best one can do is to trade off execution time for reliability or vice versa, according to users' needs. Furthermore, there is a need for an algorithm which can assign tasks of an application to satisfy both of the objectives to some degree. Motivated from these facts, two different algorithms, which are capable of trading off execution time for reliability, are developed. To enable the proposed algorithms to account for the reliability of resources in the system, an expression which gives the reliability of the application under a given task assignment is derived. The simulation results are provided to validate the performance of the proposed algorithms.

In this paper, two cost functions that can be incorporated into a matching and scheduling algorithm for tasks with precedence constraints are introduced to enable the algorithm to consider the reliability of different resources in the system while making decisions. The cost functions introduced are unique in the sense that they are not restricted to tree-based networks and a specific matching and scheduling algorithm. As an example, cost functions are applied to a compile time, static list scheduling heuristic. The simulation results confirm that the proposed cost functions can be exploited to produce task assignments where the effect of failures of machines and network resources on the execution of the application is reduced.

This paper presents several recursive heuristic methods for multicasting in all-port dimension-ordered wormhole-routed hypercubes. The methods described are stepwise contention-free and are primarily designed to reduce the number of communication steps required to complete the multicast operation. Comparisons show that the number of steps can be significantly reduced compared to depth contention-free solutions previously described. These methods are also shown to be source-controlled depth contention-free and can be considered a generalization of the broadcast method described previously, which is the most efficient method known.

In this paper, a method for estimating task execution times is presented in order to facilitate dynamic scheduling in a heterogeneous metacomputing environment. Execution time is treated as a random variable and is statistically estimated from past observations. This method predicts the execution time as a function of several parameters of the input data and does not require any direct information about the algorithms used by the tasks or the architecture of the machines. Techniques based upon the concept of analytic benchmarking/code profiling are used to characterize the performance differences between machines, allowing observations from dissimilar machines to be used when making a prediction. Experimental results are presented which use actual execution time data gathered from 16 heterogeneous machines.

This paper presents a novel technique for routing in wormhole-switched multiprocessor interconnection networks with clustered configuration. The network model used here consists of a set of clusters interfaced through a common central network. We assume that the central network and the clusters use independent algorithms to route messages between their internal nodes. A technique for deriving a global routing algorithm based on the local algorithms is presented, which allows the transfer of messages between any pair of nodes in the network. This proposed method is shown to be deadlock-free with two virtual channels. The clustered network model and the proposed routing technique can be used to enhance the fault tolerance capability of existing routing algorithms. In particular, we describe fault-tolerant routing methods for meshes, which can tolerate any arbitrary fault distribution without disabling connected healthy nodes.

The problem of scheduling directed acyclic task flow graphs to multiprocessor systems using point-to-point networks is examined. An environment where the application has a strict throughput requirement is assumed. Pipelined parallelism is used to meet the throughput requirement. Communication and computation are completely overlapped. Each task and message has a periodic rate and deadline equal to the throughput requirement. A heuristic procedure based on preclustering, recursive mincut bipartitioning, and iterative improvement is proposed to reduce the maximum contention due to communication in the network, increasing the likelihood that messages meet their deadlines. The task assignment procedure takes into account the topology of the multiprocessor system and the distance between communicating tasks.

This paper presents a novel technique for routing in wormhole-switched clustered networks. The network model consists of a set of clusters interfaced through a common central network. First, a global routing algorithm is derived based on the local algorithms used for routing within clusters. This proposed algorithm is shown to be deadlock-free with two virtual channels. This method is then applied for fault-tolerant routing in meshes, without disabling any of the connected healthy nodes.

Real-time applications when mapped to distributed memory multiprocessors produce periodic messages with an associated deadline and priority. Real-time messages may be hard or soft deadline. Real-time extensions to wormhole routing (WR) with multiple virtual channels (VCs) and priority-based physical link arbitration and VC allocation have been proposed in the literature. With a fixed number of VCs/link, a message can face an unbounded priority inversion, rendering the global priority ineffective. In this paper, we propose a new flow control mechanism called Preemptive Pipelined Circuit Switching for Real-Time messages (PPCS-RT) to reduce the priority inversion problem. For the proposed model, with some architectural support, we present an off-line approach to compute delivery guarantees of hard deadline real-time messages. We also perform a comparison of real-time WR and PPCS-RT in terms of performance with soft deadline traffic. The overall miss ratio percentage is over 30 percent higher for WR than PPCS-RT with one VC/link at high traffic loads. Finally, we compare the architectural complexity of a PPCS-RT router and other real-time routers.

This paper presents several recursive heuristic methods for multicasting in all-port dimension-ordered wormhole-routed hypercubes. The methods described are stepwise contention-free and are primarily designed to reduce the number of communication steps. Experiments show that the number of steps can be significantly reduced compared to depth contention-free solutions previously described. These methods are also shown to be source-controlled depth contention-free and can be considered a generalization of the broadcast method described by C.T. Ho and M. Kao (1995) which is the most efficient method known.

In this paper we present a strongly fault-tolerant design for the k-ary n-cube multiprocessor and examine its reconfigurability. Our design augments the k-ary n-cube with (/sup k///sub j/)/sup n/ spare nodes; each set of j/sup n/ regular nodes is connected to a spare node and the spare nodes are interconnected as a (/sup k///sub j/)-ary n-cube. Our approach utilizes the circuit-switched capabilities of the communication modules of the spare nodes to tolerate a large number of faulty nodes and faulty links without any performance degradation. Both theoretical and simulation results are presented.

An efficient run time, statistical scheme for estimating the execution time of a task is presented, in order to facilitate run time matching and scheduling in a distributed heterogeneous computing environment. This scheme is based upon a nonparametric regression technique, where the execution time estimate for a task is computed from past observations. Furthermore, this technique is able to compensate for different parameters upon which the execution time depends, and does not require any knowledge of the architecture of the target machine. It is also able to make accurate predictions when erroneous data is present in the set of observations, and has been experimentally shown to produce estimates with very low error even with few past values from which to calculate a new estimate.

A parallel sorting algorithm for sorting n elements evenly distributed over 2/sup d/ p nodes of a d-dimensional hypercube is presented. The average running time of the algorithm is O((n log n)/p+p log 2n). The algorithm maintains a perfect load balance in the nodes by determining the (kn/p)th elements (k1,. . ., (p-1)) of the final sorted list in advance. These p-1 keys are used to partition the sorted sublists in each node to redistribute data to the nodes to be merged in parallel. The nodes finish the sort with an equal number of elements (n/p) regardless of the data distribution. A parallel selection algorithm for determining the balanced partition keys in O(p log2n) time is presented. The speed of the sorting algorithm is further enhanced by the distance-d communication capability of the iPSC/2 hypercube computer and a novel conflict-free routing algorithm. Experimental results on a 16-node hypercube computer show that the sorting algorithm is competitive with the previous algorithms and faster for skewed data distributions.>

Algorithms for logic and fault simulation, developed and implemented on the Cray Y-MP supercomputer, a general-purpose shared-memory parallel machine with vector processors, are presented. The parallel-and-vector version of the event-driven logic simulation algorithm achieves a speedup of 52 on the Cray Y-MP with eight processors, with a maximum performance of about 2 million events per second. These results are comparable to the performance of hardware simulation engines and can be implemented on other parallel machines without major modifications. The second algorithm is a parallel and vector version of the parallel fault simulation algorithm. Experimental results on benchmark circuits show that very high evaluation rates (20 to 32*10/sup 9/ evaluations/s.) can be achieved. Speedup factors of 45 to 69 are observed between the scalar and the parallel-and-vector execution of the fault simulator.>

The authors propose logic simulation techniques using parallel and vector machines to reduce the simulation time of large digital circuits. Three algorithms for logic simulation have been developed and implemented on the Cray Y-MP supercomputer, a general-purpose shared-memory parallel machine with vector processors. The first is a vector version of the event-driven algorithm that achieves a speedup of 13.6 on a single Cray Y-MP processor. The second is a parallel version of the event-driven algorithm that achieves a speedup of 6.3 with eight processors. The third is a complete parallel and vector version of the event-driven algorithm that achieves a speedup of 52 on the Cray Y-MP with eight processors. The proposed techniques are very general so that they can be implemented on other computers without major modifications. Comparisons between the three algorithms and commercial logic simulators are included.>

A highly vectorizable parallel fault simulation algorithm for high-speed fault simulation of combinational circuits, developed to take advantage of the specific hardware architecture of the Cray X-MP vector supercomputer, is described. The algorithm takes into account the memory organization of the supercomputer, reduces the number of vector fetches per gate simulation, and overlaps computation and I/O. Experimental results on large benchmark circuits show that very high evaluation rates (3.0-3.5*10/sup 9/ evaluations/s) comparable to those of hardware logic simulation energies can be achieved. Speedup factors of 50-60 observed between scalar and vector execution of the simulator on the Cray X-MP/28 are reported.>

The problem of detection and identification of a faulty processing element in a systolic array is addressed. A method for designing processing elements with concurrent error detection is presented. The mod gAN mod /sub M/ code is shown to be an effective code for encoding the operands in a systolic array. It is shown that the mod g3N mod /sub M/ code is equivalent to a residue code with the check and information bits interchanged, for an odd number of information bits. This allows arithmetic to be performed separately on the information and check bits while the output can be checked by an AN checker. An architecture and rules for designing a self-checking processing element (PE) for systolic arrays are presented. Both redundancy and extra delay of the self-checking PE are shown to be low.>

A highly vectorized parallel fault simulation (VPFS) algorithm developed to take advantage of the specific hardware architecture of the Cray X-MP is described. The data structure is optimized to suit the constraints imposed by the design of the main memory on the Cray supercomputer. The implementation of VPFS on a Cray X-MP/24 achieved a peak performance of about 2.5*10/sup 9/ gate evaluations per second on one processor, for a maximal speedup of approximately=30 over scalar processing.>

Finite-element discretization produces linear equations in the form Ax=b, where A is large, sparse, and banded with proper ordering of the variables x. The solution of such equations on distributed-memory message-passing multiprocessors implementing the hypercube topology is addressed. Iterative algorithms based on the conjugate gradient method are developed for hypercubes designed for coarse-grained parallelism. The communication requirements of different schemes for mapping finite-element meshes onto the processors of a hypercube are analyzed with respect to the effect of communication parameters of the architecture. Experimental results for a 16-node Intel 80386-based iPSC/2 hypercube are presented and discussed.>

This paper describes a navigation algorithm for a vehicle equipped with a laser rangefinder sensor. The navigation algorithm is broken up into four parts, region classification, path planning, path smoothing, and path execution. Algorithms for region classification, path planning and path smoothing are presented. The navigation system was tested, and shown to produce fast, reliable results, in areas containing a high percentage of obstacles.

A method for the deductive fault simulation of faults in inverter-free circuits is presented. It is shown that in an inverter-free circuit, fault lists on lines with complementary logic values are disjoint, and fault list calculations can be done by performing fewer set operations compared to conventional gate level deductive simulation. Applications of the method to programmable logic arrays (PLA's) and deductive fault simulation of PLA faults are discussed.

The paper describes a reliable multiprocessor system designed for real time control applications and specifically applied to the control of a six legged walking machine. The system consists of four Intel 8086 based computers with four buses and can execute tasks in parallel or in a redundant configuration with two or three processors executing the same task in a loosely synchronized manner. The system is continuously reconfigured so that every processor gets checked out by participating in a redundant configuration. A combined hardware-software scheme is used for voting. Hardware comparators compare outputs of pairs of processors whereas buffer selection, fault identification and error correction are done by software. Thus advantages of both hardware and software schemes are exploited. The hexapod is simulated by a fifth computer.

An algorithm for generating test patterns for combinational circuits has been developed and programmed. The algorithm is definitive and finds a test for all faults including those that require multiple paths to be sensitized, by sensitizing a single path at a time and trying at most each single path. This is achieved by using a new calculus based on nine values (0,1,D,D̄,0/D,0/D̄, 1/D,1/D̄,U). One path is deliberately sensitized while the alternative paths are assigned values which permit the option of desensitizing or sensitizing them as the sensitized path is developed. Experimental results are presented for a variety of cases.