1571256
Parallelism analyzers for parallel discrete event simulation
Discrete event simulation is usually time consuming. Recently, there has been a great deal of interest in using parallel computers to speed up the simulation process. Before the parallel simulation approach is applied, it is important to understand the inherent parallelism of simulation applications. A simple technique called critical path analysis was proposed to study paralllelism of simulation applications. This paper describes three critical path analysis algorithms based on different event-scheduling (process scheduling) policies. These algorithms are much simpler than a previous approach, where the events must be recorded in a trace and an extra pass is required to process the event trace. In our approach, the critical path analysis algorithms are integrated with the sequential simulation. At the end of the sequential simulation, the optimal parallel execution time is also computed. Livny proposed an algorithm similar to our approach (His, however, was designed for a specific language). Our algorithms can be integrated with sequential simulation programs written by users or be integrated with simulation languages. Another advantage of our algorithms over previous approaches is that ours can be used to study load balancing under different event-scheduling policies. Since our algorithms can be easily inserted in sequential simulation programs, critical path analysis can be applied to existing sequential programs without difficulty. The results can then be used to predict the performance of parallel simulation on similar applications. An example is given to show how useful information can be obtained from our algorithms.
16744149
Performance Analysis for Dual Band PCS Networks
In a dual band personal communications services (PCS) network, heavy traffic areas are covered by microcells which overlay macrocells. In such a network, microcells and macrocells utilize different frequency bands. We propose an analytic model to study the performance of a dual band PCS architecture. Our model assumes that a PCS subscriber has a general residence time distribution in a microcell and the macrocell residence time distribution is derived from the microcell residence time distribution. An iterative algorithm is used to compute the overflow traffic from a microcell to its overlaid macrocell. Then, the call incompletion probability is computed by a macrocell model based on the overflow traffic. Our study indicates that the variance of the microcell residence time distribution and the number of microcells covered by a macrocell have significant effects on the call incompletion probability.
2805042
A new random walk model for PCS networks
This paper proposes a new approach to simplify the two-dimensional random walk models capturing the movement of mobile users in personal communications services (PCS) networks. Analytical models are proposed for the new random walks. For a PCS network with hexagonal configuration, our approach reduces the states of the two-dimensional random walk from (3n/sup 2/+3n-5) to n(n+1)/2, where n is the layers of a cluster. For a mesh configuration, our approach reduces the states from (2n2-2n+1) to (n/sup 2/+2n+4)/4 if n is even and to (n/sup 2/+2n+5)/4 if n is odd. Simulation experiments are conducted to validate the analytical models. The results indicate that the errors between the analytical and simulation models are within 1%. Three applications (i.e., microcell/macrocell configuration, distance-based location update, and GPRS mobility management for data routing) are used to show how our new model can be used to investigate the performance of PCS networks.
5110930
A comparison study of the two-tier and the single-tier personal communications services systems
A two-tier PCS system integrates the high tier PCS system and the low tier PCS systems into a single system to provide the advantages of both tiers. Such a system is expected to provide better service (more available and more cost effective to the users) at the expense of the extra tier switching management. We compare the performance of the two-tier PCS system and the single low tier system in two aspects: the registration traffic and the service availability. Because of the tier management, the two-tier system generates more registration traffic than the single low tier system. Under the range of the input parameters in our study, we show that the two-tier system generates less than 10% extra registration traffic than the single low tier system in most cases and generates less than 20% registration traffic in the worst cases. It is clear that for the service availability, the two-tier system is better than the single one tier system. We also study the probability that a call is forced terminated in the single low tier system because the low tier becomes unavailable during the call (such a call can be continued in the two-tier system).
22500122
Performance of hot billing mobile prepaid service
Abstract Prepaid service has become an important mobile application with rapid growth for subscription rate in the recent years. Implementation of prepaid service may generate large network traffic that significantly affects the performance of a mobile network. This paper studies the hot billing solution for prepaid service. We investigate how the amount of prepaid credit and the frequency of call detail record (CDR) transmissions affect network signaling and potential bad debt that a service provider may bear. Our study suggests that a prepaid service provider should encourage customers to buy large prepaid credits by giving them discounts. Furthermore, based on call traffic, an optimal CDR transmission frequency can be found by using our modeling technique.
15619003
A Graphical User Interface Design for Network Simulation
Abstract This article describes a prototyping effort of a flexible graphical user interface (GUI) for a simulation tool called COPS. The GUI is designed to allow parameter setup for all modules in simulation model, and can be easily replaced by new GUIs implemented in different languages/graphical tools. This article provides design guidelines and implementation details of the flexible GUI.
6763648
An effective methodology for functional pipelining
We address the problem of given a loop behavior, a target initiation interval and resource constraints, scheduling a loop in a pipelined fashion such that the iteration time (turn-around time) is minimized. The iteration time is an important quality measure of a data path design because of its direct correlationship with both the storage and the control costs. Our scheduler starts with performing an As Soon As Possible Pipelined (ASAPp) scheduling without regard to the resource constraint. It then resolves the resource constraint violations, if there are any, by repeatedly rescheduling some operations.
6671545
LES: A Layout Expert System
In this paper we describe an expert system for layout generation in a hierarchical VLSI design system. It applies a combination of rule- and algorithmic-based techniques on a new layout style. Experimental results have demonstrated the superiority of this expert system against various standard-cell systems and its competitiveness with human designers.
195838317
Data path allocation based on bipartite weighted matching
Proposes a graph-theoretic approach for the data path allocation problem. The problem is decomposed into three subproblems: (1) register allocation, (2) operation assignment, and (3) connection allocation. The first two subproblems are modeled as two bipartite weighted matching problems and solved using the Hungarian method. The third subproblem is solved using a greedy method. It is shown that, by taking the other into consideration while solving one, equally satisfactory results can be obtained, regardless of the order in which (1) and (2) are performed. Two programs, LYRA and ARYL, are implemented which solve the subtasks in different orders. For register allocation, the approach is the first one to guarantee minimal use of registers while being able to take the interconnection cost into account. This research has demonstrated that the bipartite weighted matching algorithm is indeed a good solution for the data path allocation problem.<<ETX>>
28386887
New Systolic Arrays for the Longest Common Subsequence Problem
Abstract New systolic arrays are presented to solve the longest common subsequence (LCS) problem. The first array is based on a previous work to compute the length of an LCS. The second array improves on the first one. The second array is about 1 4 faster than the first array, and each processing element (PE) of the second array requires one less port for both input and output to transfer one less value. Either of the two arrays can be equipped with a content-addressable memory in each PE to recover an LCS. The resulting array requires fewer steps than the previously proposed one.
16396963
Performance-driven interconnection optimization for microarchitecture synthesis
This paper addresses the interconnection synthesis problem in microarchitecture-level designs. With emphasis on the speed of data movement operations, we propose algorithms that take into consideration the effect of each data-transfer-to-bus binding on the data transfer delay time. The delay time is calculated as a function of both data source load and data carrier (bus) load. By balancing loads among hardware components, the data transfer delay time (hence the total execution time) is shortened. We consider two types of problems: resource-constrained binding and performance-constrained binding. Two integer linear programming (ILP) formulations are derived to optimally solve the problems. In order to speed up the computation, a bipartite weighted matching method for the resource-constrained binding and a greedy merging method for the performance-constrained binding are also proposed. Both the ILP formulation generators and the heuristics have been programmed. Experimental results indicate that the proposed algorithms are indeed very effective in optimizing the performance aspect of the interconnection design. >