Browsing by Author "Xiao, Zhonge"

Now showing 1 - 5 of 5
  • No Thumbnail Available
    ItemOpen Access
    NOTES ON PARALLELIZING ATM-TN CELL-LEVEL SIMULATION MODELS
    (1998-07-01) Xiao, Zhonge
    This is a facts finding study for parallelizing ATM-TN simulation models. ATM-TN stands for ATM Traffic and Network. It is a frame work for detailed cell level ATM simulation models. The users are responsible for providing network topology and specifying parameters for each component of the network being modeled. To a large extent, the principles presented in this report also apply to other cell level ATM simulation models. The purpose of the study is to find out what is the available parallelism in this type of ATM-TN models, how to parallelize the models in general, and what problems there are to be addressed for the Time Warp mechanism to get reasonable speedup with the ATM-TN simulation given the very small granularity of the simulation models.
  • No Thumbnail Available
    ItemOpen Access
    Report on WarpKit performance study and improvement
    (1998-07-01) Xiao, Zhonge; Unger, Brian W
    This is a report on the earlier development of WarpKit, a parallel simulation kernel based on shared-memory multi-processor architecture, as part of the Telesim project. The development is aimed at exploiting shared memory multi- processor paradigm and developing a Parallel Discrete Event Simulation package which is based on shared memory multi-processors and capable of delivering high performance. Three major problems that have great impact on the performance of Time Warp systems are: excessive cost incurred by rollback computation resulting from sole reliance on rollback as a basic synchronization mechanism in a distributed/parallel processing system, large amount of memory space required to run applications, and high system overheads in inter-process communication and global control (e.g. GVT computation and memory management). Shared memory multi-processor architecture provides the potential of delivering much higher performance for Time Warp systems than can be achieved in distributed environment. New approaches could be conceived to address these problems and to realize the potential. This report covers the results of our effort to improve WarpKit Kernel performance. Incremental State Saving has been implemented on top of existing Kernel which reduces both the time and space spent on state saving, a necessity of Time Warp. Purely asynchronous schemes have been developed and implemented for the global control mechanism. As a result, the system overhead on global control has been reduced significantly. The new global control mechanism also makes the system overheads insensitivity to the number of processors as opposed to the distributed situation where system overhead experiences a sharp increase with the number of processors. A global scheduling and load balancing mechanism is expected to restrict the number of rollbacks to a low percentage over net events to be processed by the Kernel. With these new mechanisms in place, one may expect close to linear speedup curve for parallel discrete event simulation on shared memory multi- processors.
  • No Thumbnail Available
    ItemOpen Access
    Rule trees an execution mechanism for time-ordered forward deduction evaluating strategy of Starlog
    (1998-07-01) Xiao, Zhonge; Cleary, John; Unger, Brian W
    This is the second report on "Time-ordered Forward Deduction" algorithm for Starlog. A \fBRule Tree (R-tree)\fR structure is discussed. The R-tree is used to represent a program rule in the dynamic process of program execution. It serves not only as a structured data storage for program rules and their derivable instances, but also as a control structure in program execution which allows the execution to be carried out in more orderly and formal manner.
  • No Thumbnail Available
    ItemOpen Access
    Time-ordered forward deduction a bottom-up evaluation strategy for Starlog
    (1998-07-01) Xiao, Zhonge; Cleary, John; Unger, Brian W
    Starlog, a Horn clause logic programming language, allows for time stamps, interval arithmetic, and negations. A bottom-up evaluation strategy, called "Time-ordered Forward Deduction", for the language is described. The algorithm heavily relies on time stratification as its basic execution control mechanism. A conservative approach has been adopted to handle negations, which defers the evaluation of negations until it is safe to do so. Various techniques to deal with subtle cases of inter-clause relations in negation evaluation are discussed. To illustrate the algorithm, some simple but non-trivial example programs are presented.
  • No Thumbnail Available
    ItemOpen Access
    Time-ordered forward deduction with negation evaluation strategy revised
    (1998-07-01) Xiao, Zhonge; Cleary, John; Unger, Brian W
    This is the third report on "Time-ordered Forward Deduction" algorithm for Starlog. The negation evaluation part of the algorithm has been modified extensively based on experiments with previous implementations and further study. The new algorithm is optimistic in terms of its negation evaluation strategy. The notion of \fBOpen Tuple\fR and related \fBNegation Failure Bound Splitting (NFBS)\fR method are introduced. A complete definition of the new algorithm is given, it treats the execution of a program in a more consistent and uniform manner and does not involve any semantic aspects of a program. It is our belief that a formal proof of the algorithm is not too difficult.