Search

This thesis documents a procedure for implementing the Revolving Cylinder scheduling algorithm for parallel programs on the ECOS Workstation System (EWS), designed specifically by AT&T for simulation of the Enhanced Modular Signal Processor (EMSP) currently in use by the United States Navy. The Revolving Cylinder (RC) algorithm provides a methodology for forcing First Come First Served (FCFS) schedulers to follow a more systematic utilization of available resources. The methods of implementation used take advantage of the Graphical Editor (gred) to insert additional data dependencies into the program structure. The thesis utilizes applications written in Signal Processing Graph Notation (SPGN), viz., a simple correlator function and the active subroutine of the U.S. Navy Sonobuoy benchmark. Results for standard FCFS scheduling and RC modified scheduling are presented for both. Special attention is paid throughout the thesis to enhancement of manufacturer supplied documentation with regard to implementation of the non-standard RC structures. Impact of the algorithm on throughput and latency is discussed, as well as performance determination using the tools provided with the ECOS Workstation System, http://archive.org/details/largegraindatafl1094526609, Lieutenant, United States Navy, Approved for public release; distribution is unlimited.

This thesis is in support of the on-going Autonomous Underwater Vehicle (AUV) project at the Naval Postgraduate School in Monterey, California. This work investigates the development of a transputer-based multiprocessor and how to program it using Ada. The objective is to create a software layer that enables intertask communication over a network of transputers to be location invariant and to make the communication process transparent to the user. Ada, being a concurrent high level language, was chosen as the language in which this software layer is to be written. The method of intertask communication developed here captures the Ada rendezvous semantics, provides reliable and efficient delivery of messages between tasks regardless of their locations, and uses a common message format for all communicating tasks. The location invariant property makes the software layer particularly suitable for developing higher level allocation algorithms. The communication is handled by generic tasks common to each transputer and a common mapping function that has the locations of all the tasks. The programmer needs only to conform to a common format of communication when sending messages between tasks and not be concerned with the actual delivery of the message. The software developed was successfully tested and its performance analyzed for a five transputer ring network using the AUV-II data-flow diagram., http://archive.org/details/onprogrammingtra1094526664, Lieutenant, United States Navy, Approved for public release; distribution is unlimited.

This thesis deals with the features and performance of a network interface device to interconnect two remote Fiber Distributed Data Interface (FDDI) Local Area Networks (LANs) through the Critical Data Link (CDL) which is a full-duplex, jam-resistant, point-to-point microwave communications system for use in imagery and signals intelligence collection systems. In particular, OPNET, a commercially available network engineering tool is used to model a medium access level remote bridge interface connecting two LANs. The effectiveness of two different load balancing techniques used to distribute traffic over the multiple channels of the CDL has been studied. Also, the effect of different jamming patterns on the bit error rate seen by the users has been studied, http://archive.org/details/datlinklevelinte1094528089, NA, NA, Turkish Navy author.

Fast, ultra-reliable, real-time computing is fundamental in today's weapons system. Increased system throughput and reliability can be achieved by utilizing distributed systems in which a single application program executes on multiple processors, connected to a network. The distributed nature of such systems make it possible to tolerate failures and react to overloads without the application level performance degrading unacceptably. Fault tolerance in these systems typically involves fault detection and recovery. Repair following failure involves smooth integration of the repaired processor and subsequent reconfiguration. These actions must take place transparently, that is without the application program noticing it. Therefore, sufficient information must be maintained through the use of checkpointing to describe the state of the system at any time and ensure correct operation after failure/repair. This thesis investigates a possible framework for achieving a fault- tolerant realtime distributed system which provides transparent function-to-function message passing, status monitoring using periodic health messages and maintains a globally consistent system state by carrying out independent checkpointing procedures. The proposed scheme is simulated using concurrent Ada processing for a four node, twelve function, distributed system., http://archive.org/details/reconfigurationi1094526720, Lieutenant, United States Navy, Approved for public release; distribution is unlimited.

Directed Acyclic Graph Scheduling is a technique used to implement the real-time execution of Digital Signal Processing applications on multiple- processor data-flow machines that support variable-grained parallelism. The approach used in the Navy's AN/UYS-2 Digital Signal Processor statically schedules an application graph at run-time using a First-Come-First-Served (FCFS) policy. Research by Shukla and Zaky Shukla 91 developed a new algorithm, the Revolving Cylinder(RC), to ameliorate the inherently non-deterministic output flow of the FCFS scheduling approach currently used in the system. Although the RC technique solved the problem of output-flow determinism there was no broad coverage of other current research in the very specialized field of real-time data-flow machines. This thesis reviews Revolving Cylinder analysis and then surveys, compares, and evaluates research in the field using the review as a baseline for comparison. The RC approach is best at improving the throughput and output flow determinism of a narrow range of applications on a particular architecture. Each of the other approaches offer improvements over RC scheduling in either performance as measured by throughput or through flexibility in applications handled. For each of these improvements, however, significant trade-offs are made and so improvements become relative when they affect system robustness and an ability to handle repeated execution of application graphs. The AN/UYS-2 can implement RC scheduling with a minimum of cost and no hardware reconfiguration and this makes it the best approach for short-term system, http://archive.org/details/schedulingtechni1094526752, Captain, United States Army, Approved for public release; distribution is unlimited.

This thesis presents a globally scalable, decentralized group membership service to manage client process groups operating in a distributed, asynchronous environment. This group membership service is totally scalable, handling process groups spanning a single LAN to groups spanning the entire global Internet equally well. It provides for nested and overlapping groups, as well as multiple groups residing on a single LAN. It also provides various Quality of Service selections which permit individual groups to be configured for an optimal balance between high quality with strong consistency semantics for group membership, and weaker consistency semantics with reduced complexity and latency. This thesis describes the complete design of the protocol used to implement the group membership service. It presents the design requirements and goals, and underlying assumptions about the network. The various Quality of Service selections provided by the group membership service are described in detail, as well as the interface between the process groups, the membership service, and the underlying network. The use of a hierarchical architecture to obtain the desired scalability, flexibility, and robustness is explained. A proof of correctness for the protocol is presented, and a partial implementation of the group membership service is described, http://archive.org/details/ascalabledecentr1094528514, Lieutenant, United States Navy, Approved for public release; distribution is unlimited.

The Optimized Network Engineering Tool (OPNET) is a commercially available communications network simulation package. This thesis involves the modification of OPNET's Fiber Distributed Data Interface Local Area Network (FDDI LAN) model in order to enhance its usefulness as an aid in the development of recommendations for the characteristics and metrics to be eventually included in the Defense Service Project Office's (DSPO) Common Data Link (CDL) project. This work includes a step-by-step guide for FDDI simulation in OPNET, and a discussion of the changes made to the original model to enhance its performance and data display characteristics. Simple tests are provided to verify the completed model's performance and usefulness as a working tool for further development, http://archive.org/details/modelingndsimula1094528371, Lieutenant, United States Navy, Approved for public release; distribution is unlimited.

In this thesis, Large Grain Data Flow (LGDF) representation of parallelism is applied to throughout-critical applications that process periodically arriving data. The applications are represented by directed acyclic graphs in which a vertex represents an indivisible node program execution and an arc represents data flow from its source node to sink node. The machine and graph parameters are assumed to be such that the time to transfer one unit of data is comparable to the time to execute one operation at a processor. The machine model consists of a set of processors connected to a set of memory modules by a cross-bar interconnection network Execution of LGDF graphs on such machines either requires a run-time mechanism to dispatch executable nodes on available processors or a compile-time static scheduling of nodes to processors. The former approach, although flexible and robust, suffers from contention- related overhead and the latter, although capable of eliminating contention, is rigid and computationally intensive. It is shown by simulation that throughput can be improved when compile-time graph restructuring is coupled with simple first-come-first-serve dispatching. The restructuring is based on selectively adding control dependencies between graph nodes. This technique, called the revolving cylinder analysis, is shown to be an effective framework for achieving communication/computation overlap and reducing memory contention, http://archive.org/details/usefulnessofcomp1094526318, Captain, United States Army, Approved for public release; distribution is unlimited.

This thesis discusses the theory behind collision based and noncollision based network protocols. From this basis, a complete theoretical performance analysis is performed on both Ethernet and FDDI. The CAPSnet FDDI installation is discussed and evaluated. Actual performance tests for both Ethernet and FDDI are provided and the results are discussed in detail. The test results are compared and analyzed. Actual performance is compared to theoretical performance. An explanation is provided to explain why actual performance does not match theoretical performance., http://archive.org/details/fddiinstallation1094523674, LT, USCG, Approved for public release; distribution is unlimited.

A group membership protocol ensures agreement and consistent commit actions among group members to maintain a sequence of identical group views in spite of continuous changes, either voluntary or otherwise, in processors' membership status. In asynchronous distributed environments, such consistency among group views must be guaranteed using messages over a network which does not bound message delivery times. Assuming a network that only provides a reliable, FIFO channel between any pair of processors, one approach to designing such a protocol is to centralize the responsibility to detect changes, ensure agreement, and commit them consistently in a single manager process. This approach is complicated by the fact that a protocol to elect a new manager with a consistent membership proposal must be executed when the manager itself fails. In this thesis, a membership protocol based on ordering of group members in a logical ring that eliminates the need for such centralized responsibility is presented. Agreement and commit actions are token-based and the protocol ensures that no tokens are lost or duplicated due to changes in membership. It is able to process continuous changes to the membership, does not depend upon any majority-based decisions, and processes joins and departures identically. The cost of committing a change is always 2n point-to-point messages over FIFO channels where n is the group size. The protocol correctness is proven in a formal framework. The implementation details for the protocol to execute on a network of SUN workstations are presented. Detailed examples of the behavior of the protocol for various sequences of changes to group membership is presented. The programs for various client-server communication patterns used for interfacing various functions are also presented., http://archive.org/details/designndimplemen1094523625, Scientist, DoD India, Approved for public release; distribution is unlimited.

Alternative computer architectures are necessary to replace the traditional 'von Neumann' computer organization in order to obtain large increases in performance. The traditional 'von Neumann' architecture uses a timer based (e.g., the program counter), sequentially programmed, single processor approach to problem solving. Today's new hardware technology allows for the utilization of multiple processors. By programming and operating these processors in parallel, this alternative architecture will provide for greater computing speed, improved system reliability, enhanced software manageability, and a more cost-effective approach than our present computing practices., http://archive.org/details/networkedworksta1094524199, Lieutenant, United States Navy, Approved for public release; distribution is unlimited.

Entities cooperating as a group become simpler to construct if they possess access to a membership service to manage and administer the membership information of such groups. This report describes the architecture and design of a wide-area group membership service. Unlike any known membership service, the service is based on a completely decentralized protocol executed by a hierarchy of servers. This hierarchy permits a clear separation between the membership service infrastructure and support for application groups, permitting global scaleability. The membership protocol itself is executed by a core set of membership servers identified in a group-specific manner, permitting a separate name space, membership scope and partition handling for each group. We describe a suitable application programme's interface and provide correctness arguments for the protocol. A working implementation of the basic membership protocol is described.

Entities cooperating as a group become simpler to construct if they possess access to a membership service to manage and administer the membership information of such groups. This report describes the architecture and design of a wide-area group membership service. Unlike any known membership service, the semce is based on a completely decentralized protocol executed by a hierarchy of servers. This hierarchy permits a clear separation between the membership service infrastructure and support for application groups, permitting global scaleability. The membership protocol itself is executed by a core set of membership servers identified in a group-specific manner, permitting a separate name space, membership scope and partition handling for each group. We describe a suitable application programmer's interface and provide correctness arguments for the protocol. A working implementation of the basic membership protocol is described.

This report addresses the problem of constructing multicast trees with reservation of resources. The main features of the approach described are that it tolerates asymmetric traffic loads on network links and algorithmically locates data distribution centers for every multiparticipant interaction. A fast and scalable algorithm for locating distribution centers based on the network load and a priori knowledge of participant's locations and resource requirements is given. To explicitly handle cases of disjoint send and receive paths between two nodes, a protocol to build separate send-trees and receive-trees around the centers located in the manner above is given. Simulation results on various topologies are presented showing that, with the above center location mechanism, center-specific trees yield lower tree cost than source-specific trees for many concurrent senders without increasing the average path length significantly. The use of distribution centers, a priori information, and sensitivity to load asymmetry permit effective combination of center-specific and source-specific trees for an interaction and eliminate the need for symmetry checks during resource reservation. Multicast trees, Scalable, Quality of service, Wide area networks

This thesis presents a globally scalable, decentralized group membership service to manage client process groups operating in a distributed, asynchronous environment. This group membership service is totally scalable, handling process groups spanning a single LAN to groups spanning the entire global Internet equally well. It provides for nested and overlapping groups, as well as multiple groups residing on a single LAN. It also provides various Quality of Service selections which permit individual groups to be configured for an optimal balance between high quality with strong consistency semantics for group membership, and weaker consistency semantics with reduced complexity and latency. This thesis describes the complete design of the protocol used to implement the group membership service. It presents the design requirements and goals, and underlying assumptions about the network. The various Quality of Service selections provided by the group membership service are described in detail, as well as the interface between the process groups, the membership service, and the underlying network. The use of a hierarchical architecture to obtain the desired scalability, flexibility, and robustness is explained. A proof of correctness for the protocol is presented, and a partial implementation of the group membership service is described

The Optimized Network Engineering Tool (OPNET) is a commercially available communications network simulation package. This thesis involves the modification of OPNET's Fiber Distributed Data Interface Local Area Network (FDDI LAN) model in order to enhance its usefulness as an aid in the development of recommendations for the characteristics and metrics to be eventually included in the Defense Service Project Office's (DSPO) Common Data Link (CDL) project. This work includes a step-by-step guide for FDDI simulation in OPNET, and a discussion of the changes made to the original model to enhance its performance and data display characteristics. Simple tests are provided to verify the completed model's performance and usefulness as a working tool for further development

This thesis describes the issues involved in node allocation for a Large Grain Data Flow (LGDF) model used in Navy signal processing applications. In the model studied, nodes are assigned to processors based on load balancing, communication/computation overlap, and memory module contention. Current models using the Revolving Cylinder (RC) technique for LGDF graph analysis do not adequately address node allocation. Thus, a node to processor allocation component is added to a computer simulator of an LGDF graph model. It is demonstrated that the RC technique, when proper node allocation is taken into account, can improve overall throughput as compared to the First-Come-First- Served (FCFS) technique for high communication/computation costs

This thesis deals with the features and performance of a network interface device to interconnect two remote Fiber Distributed Data Interface (FDDI) Local Area Networks (LANs) through the Critical Data Link (CDL) which is a full-duplex, jam-resistant, point-to-point microwave communications system for use in imagery and signals intelligence collection systems. In particular, OPNET, a commercially available network engineering tool is used to model a medium access level remote bridge interface connecting two LANs. The effectiveness of two different load balancing techniques used to distribute traffic over the multiple channels of the CDL has been studied. Also, the effect of different jamming patterns on the bit error rate seen by the users has been studied

In this thesis, we address the problem of multicast tree construction with guaranteed quality of service (QoS) in networks with asymmetric link costs. We describe a protocol to locate distribution centers for an interaction based on network load and participant location. We then describe the protocol for constructing a shared tree around the selected center. We compare the quality of the resultant trees on large hypothetical networks with that of source based trees. Additional comparisons are made with other multicast techniques such as Protocol Independent Multicasting (PIM) and Core Based Trees (CBT). Our results show that the shared trees built using our approach represent a significant improvement over other techniques when the network topology contains a large degree of asymmetry in link cost. This makes our approach the most general of all other techniques proposed to date.

This report addresses the problem of constructing multicast trees with reservation of resources. The main features of the approach described are that it tolerates asymmetric traffic loads on network links and algorithmically locates data distribution centers for every multiparticipant interaction. A fast and scalable algorithm for locating distribution centers based on the network load and a priori knowledge of participant's locations and resource requirements is given. To explicitly handle cases of disjoint send and receive paths between two nodes, a protocol to build separate send-trees and receive-trees around the centers located in the manner above is given. Simulation results on various topologies are presented showing that, with the above center location mechanism, center-specific trees yield lower tree cost than source-specific trees for many concurrent senders without increasing the average path length significantly. The use of distribution centers, a priori information, and sensitivity to load asymmetry permit effective combination of center-specific and source-specific trees for an interaction and eliminate the need for symmetry checks during resource reservation. Multicast trees, Scalable, Quality of service, Wide area networks, NSF RIA Grant 9309316, http://archive.org/details/multicasttreecon00shuk, Center of High Assurance Computing Systems Naval Research Laboratory, NA, Approved for public release; distribution is unlimited.

In this paper, the benefits of parallel computing using a workstation cluster are explored for satellite orbit prediction. Data and function decomposition techniques are used. Speedup and throughput are the performance metric studied. The software employed for parallelization was the Parallel Virtual Machine (PVM) developed by the Oak Ridge National Laboratory. PVM enables a network of heterogeneous workstations to appear as a parallel multicomputer to the user programs. A speedup of almost 6 was achieved when using 8 SUN workstations.

Alternative computer architectures are necessary to replace the traditional 'von Neumann' computer organization in order to obtain large increases in performance. The traditional 'von Neumann' architecture uses a timer based (e.g., the program counter), sequentially programmed, single processor approach to problem solving. Today's new hardware technology allows for the utilization of multiple processors. By programming and operating these processors in parallel, this alternative architecture will provide for greater computing speed, improved system reliability, enhanced software manageability, and a more cost-effective approach than our present computing practices.

This thesis documents a procedure for implementing the Revolving Cylinder scheduling algorithm for parallel programs on the ECOS Workstation System (EWS), designed specifically by AT&T for simulation of the Enhanced Modular Signal Processor (EMSP) currently in use by the United States Navy. The Revolving Cylinder (RC) algorithm provides a methodology for forcing First Come First Served (FCFS) schedulers to follow a more systematic utilization of available resources. The methods of implementation used take advantage of the Graphical Editor (gred) to insert additional data dependencies into the program structure. The thesis utilizes applications written in Signal Processing Graph Notation (SPGN), viz., a simple correlator function and the active subroutine of the U.S. Navy Sonobuoy benchmark. Results for standard FCFS scheduling and RC modified scheduling are presented for both. Special attention is paid throughout the thesis to enhancement of manufacturer supplied documentation with regard to implementation of the non-standard RC structures. Impact of the algorithm on throughput and latency is discussed, as well as performance determination using the tools provided with the ECOS Workstation System

Directed Acyclic Graph Scheduling is a technique used to implement the real-time execution of Digital Signal Processing applications on multiple- processor data-flow machines that support variable-grained parallelism. The approach used in the Navy's AN/UYS-2 Digital Signal Processor statically schedules an application graph at run-time using a First-Come-First-Served (FCFS) policy. Research by Shukla and Zaky Shukla 91 developed a new algorithm, the Revolving Cylinder(RC), to ameliorate the inherently non-deterministic output flow of the FCFS scheduling approach currently used in the system. Although the RC technique solved the problem of output-flow determinism there was no broad coverage of other current research in the very specialized field of real-time data-flow machines. This thesis reviews Revolving Cylinder analysis and then surveys, compares, and evaluates research in the field using the review as a baseline for comparison. The RC approach is best at improving the throughput and output flow determinism of a narrow range of applications on a particular architecture. Each of the other approaches offer improvements over RC scheduling in either performance as measured by throughput or through flexibility in applications handled. For each of these improvements, however, significant trade-offs are made and so improvements become relative when they affect system robustness and an ability to handle repeated execution of application graphs. The AN/UYS-2 can implement RC scheduling with a minimum of cost and no hardware reconfiguration and this makes it the best approach for short-term system

In this thesis, we address the problem of constructing multicast data distribution trees with guaranteed quality of service (QoS) for supporting multiparty interactions. We present an approach that integrates reservation with tree construction to facilita

In this thesis the benefits of parallel computing using a workstation cluster are explored for two typical Naval applications. The applications are examples of one off-line and one on-line program. The off-line program is a Navy program currently in use by the Naval Space Command in its satellite prediction model. The on-line program is a large grain data flow problem with critical throughput requirements and represents a hypothetical combat weapons system. Data and function decomposition techniques are used in both applications. Speedup and throughput are the performance metrics studied. The software employed was the Parallel Virtual Machine (PVM) by the Oak Ridge National Laboratory. PVM enables a network of heterogeneous workstations to appear as a parallel multicomputer to the user programs. PVM runs over the workstation operating system and provides the user with a set of library calls for message passing and process creation.

In this thesis, the performance of the fiber distributed data interface (FDDI) local area network is evaluated by software simulation. The network is modeled with OPNET, a communication network simulation tool. The main focus of the model is on the medium access control (MAC) and the timing requirements that need to be met for the correct behavior of the protocol. Simulation data is presented to support results from previous analytic studies of distinctive features of the protocol, including the behavior of the token rotation time, synchronous frame delays, fairness of channel access for nodes transmitting asynchronous traffic, etc. Comparisons between the simulated and theoretical results confirm the accuracy of the OPNET simulation tools and demonstrate that it may be used to model other protocols of particular interest.

A group membership protocol provides the mechanisms to ensure the consistent group views among a group-oriented distributed processes. The protocol is required to dynamically re-configure the group views among the various members in the event of a change to the group due to a new member joining or a member departing. The departure may be voluntary or involuntary. The protocol must provide a scheme to detect the failure of any of the members and re-configure the group. Multiple changes to the group must be perceived at all members in the same order. This thesis deals with a particular group membership protocol. The protocol structures the group as a logical ring. Changes to the group are accomplished using a two-phase scheme. The agreement phase consists of circulation of an agree token. Processing the token makes a pending change known to all members. The commit phase incorporates the changes in the correct order. This thesis presents an implementation of this asynchronous group membership protocol. The main feature is that the decentralized nature of the protocol eliminates the need for a dedicated coordinator of changes. The processing requirements for the protocol are likewise distributed. The processing time required to implement a change to the group is shown to have a linear relationship to the group size.

In this thesis, Large Grain Data Flow (LGDF) representation of parallelism is applied to throughout-critical applications that process periodically arriving data. The applications are represented by directed acyclic graphs in which a vertex represents an indivisible node program execution and an arc represents data flow from its source node to sink node. The machine and graph parameters are assumed to be such that the time to transfer one unit of data is comparable to the time to execute one operation at a processor. The machine model consists of a set of processors connected to a set of memory modules by a cross-bar interconnection network Execution of LGDF graphs on such machines either requires a run-time mechanism to dispatch executable nodes on available processors or a compile-time static scheduling of nodes to processors. The former approach, although flexible and robust, suffers from contention- related overhead and the latter, although capable of eliminating contention, is rigid and computationally intensive. It is shown by simulation that throughput can be improved when compile-time graph restructuring is coupled with simple first-come-first-serve dispatching. The restructuring is based on selectively adding control dependencies between graph nodes. This technique, called the revolving cylinder analysis, is shown to be an effective framework for achieving communication/computation overlap and reducing memory contention

For development of group-oriented distributed applications, a group membership protocol provides the mechanisms to dynamically adapt to changes in the membership, ensuring consistent views among all members of the group. This is achieved, by executing a distributed script, that implements a protocol, at each member to maintain a sequence of identical views, in spite of continuous changes, either voluntary or due to failure, to the membership. In asynchronous distributed environments, the protocol has to operate over a network that does not bound delivery times. This thesis presents a decentralized membership protocol, designed to operate on asynchronous environments, that organizes the members in a logical ring. The protocol assumes reliable FIFO channels, that fully interconnect all members to be available. These assumptions are later relaxed to adapt the protocol to real-world environments. Reconfigurations of the group are carried out using a two-phase algorithm. An agreement phase makes the change known to all operational members, and a commit phase integrates the change at all members, in the correct order. The protocol supports failures of one or more members, either successive or simultaneous, voluntary departures, and joining of new members. In the case of simultaneous events, the protocol ensures that they are incorporated one at a time, and following the same sequence, at all members.

A group membership protocol ensures agreement and consistent commit actions among group members to maintain a sequence of identical group views in spite of continuous changes, either voluntary or otherwise, in processors' membership status. In asynchronous distributed environments, such consistency among group views must be guaranteed using messages over a network which does not bound message delivery times. Assuming a network that provides a reliable, FIFO channel between any pair of processors, one approach to designing such a protocol is to centralize the responsibility to detect changes, ensure agreement, and commit them consistently in a single manager process. This approach is complicated by the fact that a protocol to elect a new manager with a consistent membership proposal must be executed when the manager itself fails. In this report, we present a membership protocol based on ordering of group members in a logical ring that eliminates the need for such centralized responsibility. Agreement and commit actions are token-based and the protocol ensures that no tokens are lost or duplicated due to changes in membership. The cost of committing a change is 2n point-to-point messages over FIFO channels where n is the group size. The protocol correctness has been proven formally.

This thesis discusses the theory behind collision based and noncollision based network protocols. From this basis, a complete theoretical performance analysis is performed on both Ethernet and FDDI. The CAPSnet FDDI installation is discussed and evaluated. Actual performance tests for both Ethernet and FDDI are provided and the results are discussed in detail. The test results are compared and analyzed. Actual performance is compared to theoretical performance. An explanation is provided to explain why actual performance does not match theoretical performance.

Efficient data-flow implementation requires fast run-time mechanisms to detect and dispatch schedulable tasks. However, the inherent non-determinism in data-flow executions and the requirement of fast, and therefore, simple run- time mechanisms necessitate compile-time support to improve performance. In particular, for data-flow execution of applications, such as signal processing which are characterized by periodically received data, compile-time support can be used to control the run-time behavior to improve the predictability and efficiency. In this report, a compile-time technique that supports a simple run- time mechanism to improve throughput and predictability for a task-level data- flow programming model is described. This technique, called the revolving cylinder analysis, restructures the application, described by a task-level data- flow graph. The restructuring is based on wrapping the projected data-flow execution trace on the curved surface of a cylinder whose area depends upon the number of processors and the sum of the task execution times. The behavior of the restructured graph is shown to be more predictable under the same run-time mechanism than that of the old graph. Results on the performance improvement for two typical signal processing applications, viz., a correlator and a fast Fourier Transform, are presented. The potential of this approach in determining the optimal granularity for an application is also described. Compile-time, Data-flow, Graph Restructuring, Real-time, Run-time, Scheduling, Signal Processing, Throughput, Task-level, Naval Sea Systems Command, http://archive.org/details/realtimeexecutio00shuk, Naval Sea Systems Command, NA, Approved for public release; distribution is unlimited.

The AN/UYS-2 represents the U. S. Navy's effort to meet the signal processing demands of the 21st century. It is programmed using the Processing Graph Methodology (PGM), where signal processiog applications are reproented as graphs and the nodes specify library primitives. Presently the AN/LTYS-2 incorporates a First-Come-First-Serve run-time technique to allocate system resources to support large-grain data-flow execution. While this technique results in low run-time overhead, the system throughput degrades rapidly under high system load. To provide uniform output even under high load, a compile-time technique, called Revolving Cylinder (RC) analysis, is developed further to identify optimal chains and restructure the graph. It is shown by simulation that such chaining and restructuring improve the overall system performance.

Task allocation is an important component of the process of mapping modules of application programs to multicomputers. A scheme for static allocation of periodic tasks with precedences to processors is developed considering task execution times, communication costs, and utilization level of each processor. It has the main goal of minimizing the application response time with a minimum number of processors. A network of transputers is employed as a platform to experimentally evaluate the allocation approach constructed with this work. An existing communication layer in the language ADA is improved to provide an efficient support for task flow simulations on transputer networks. The first phase of the allocation scheme is a constructive assignment heuristic that allocates the cluster of tasks composed of all tasks in the critical path in the same processor. The remaining tasks are allocated according to a heuristic function that considers task precedences, task execution times, and relative sizes of intertask messages. The initial allocation is improved in the second phase by using an iterative pairwise interchange of tasks that considers interprocessor communication distances. The overall scheme of task allocation was successfully tested and analyzed through simulation of several applications on a transputer network providing a near optimal solution.

A group membership protocol ensures agreement and consistent commit actions among group members to maintain a sequence of identical group views in spite of continuous changes, either voluntary or otherwise, in processors' membership status. In asynchronous distributed environments, such consistency among group views must be guaranteed using messages over a network which does not bound message delivery times. Assuming a network that provides a reliable, FIFO channel between any pair of processors, one approach to designing such a protocol is to centralize the responsibility to detect changes, ensure agreement, and commit them consistently in a single manager process. This approach is complicated by the fact that a protocol to elect a new manager with a consistent membership proposal must be executed when the manager itself fails. In this report, we present a membership protocol based on ordering of group members in a logical ring that eliminates the need for such centralized responsibility. Agreement and commit actions are token-based and the protocol ensures that no tokens are lost or duplicated due to changes in membership. The cost of committing a change is 2n point-to-point messages over FIFO channels where n is the group size. The protocol correctness has been proven formally. Agreement, Asynchronous, Commit, Distributed, Failure, Group Membership, Logical Ring, Reliable Multicast, Token, Monterey, California. Naval Postgraduate School, http://archive.org/details/groupmembershipi00shuk, Monterey, California. Naval Postgraduate School, NA, Approved for public release; distribution is unlimited.

Efficient data-flow implementation requires fast run-time mechanisms to detect and dispatch schedulable tasks. However, the inherent non-determinism in data-flow executions and the requirement of fast, and therefore, simple run- time mechanisms necessitate compile-time support to improve performance. In particular, for data-flow execution of applications, such as signal processing which are characterized by periodically received data, compile-time support can be used to control the run-time behavior to improve the predictability and efficiency. In this report, a compile-time technique that supports a simple run- time mechanism to improve throughput and predictability for a task-level data- flow programming model is described. This technique, called the revolving cylinder analysis, restructures the application, described by a task-level data- flow graph. The restructuring is based on wrapping the projected data-flow execution trace on the curved surface of a cylinder whose area depends upon the number of processors and the sum of the task execution times. The behavior of the restructured graph is shown to be more predictable under the same run-time mechanism than that of the old graph. Results on the performance improvement for two typical signal processing applications, viz., a correlator and a fast Fourier Transform, are presented. The potential of this approach in determining the optimal granularity for an application is also described. Compile-time, Data-flow, Graph Restructuring, Real-time, Run-time, Scheduling, Signal Processing, Throughput, Task-level., Supersedes Rept. no. NPS-EC-92-002.

The AN/UYS-2 provides the Navy with a state of the art Digital Signal Processor. The AN-UYS-2 is programmed utilizing the Processing Graph Methodology (PGM), which represents specific tasks as nodes in a graph. It utilizes a simple First-Come-First Served (FCFS) run-time resource allocation mechanism that supports large-grain data flow processing. While the mechanism is robust, easy to implement, and results in low run-time overhead, it is difficult to predict of a given PGM will meet the application requirements. Therefor, an approach that uses compile-time analysis to exploit the periodic arrival of data and a priori knowledge of the amount of computation and communication overhead is investigated. Improvement in performance of the machine when the PGM graphs are restructures using this approach, called Revolving Cylinder scheduling, is observed; and it is found to be effective when there is a high communication overhead or when the PGM nodes are of uniform size.

This thesis is in support of the on-going Autonomous Underwater Vehicle (AUV) project at the Naval Postgraduate School in Monterey, California. This work investigates the development of a transputer-based multiprocessor and how to program it using Ada. The objective is to create a software layer that enables intertask communication over a network of transputers to be location invariant and to make the communication process transparent to the user. Ada, being a concurrent high level language, was chosen as the language in which this software layer is to be written. The method of intertask communication developed here captures the Ada rendezvous semantics, provides reliable and efficient delivery of messages between tasks regardless of their locations, and uses a common message format for all communicating tasks. The location invariant property makes the software layer particularly suitable for developing higher level allocation algorithms. The communication is handled by generic tasks common to each transputer and a common mapping function that has the locations of all the tasks. The programmer needs only to conform to a common format of communication when sending messages between tasks and not be concerned with the actual delivery of the message. The software developed was successfully tested and its performance analyzed for a five transputer ring network using the AUV-II data-flow diagram.