An efficient disk-based tool for solving very large markov models

Daniel D. Deavours, William H. Sanders

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Very large Markov models often result when modeling realistic computer systems and networks. We describe a new tool for solving large Markov models on a typical engineering workstation. This tool does not require any special properties or a particular structure in the model, and it requires only slightly more memory than what is necessary to hold the solution vector itself. It uses a disk to hold the state-transition-rate matrix, a variant of block Gauss-Seidel as the iterative solution method, and an innovative implementation that involves two parallel processes: the first process retrieves portions of the iteration matrix from disk, and the second process does repeated computation on small portions of the matrix. We demonstrate its use on two realistic models: a Kanban manufacturing system and the Courier protocol stack, which have up to 10 million states and about 100 million nonzero entries. The tool can solve the models efficiently on a workstation with 128 Mbytes of memory and 4 Gbytes of disk.

Original languageEnglish (US)
Title of host publicationComputer Performance Evaluation
Subtitle of host publicationModelling Techniques and Tools - 9th International Conference, 1997, Proceedings
EditorsRaymond Marie, Brigitte Plateau, Gerardo Rubino, Maria Calzarossa
PublisherSpringer
Pages58-71
Number of pages14
ISBN (Print)9783540631019
DOIs
StatePublished - 1997
Event9th International Conferences on Modeling Techniques and Tools for Computer Performance Evaluation, 1997 - St. Malo, France
Duration: Jun 3 1997Jun 6 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1245
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Conferences on Modeling Techniques and Tools for Computer Performance Evaluation, 1997
Country/TerritoryFrance
CitySt. Malo
Period6/3/976/6/97

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'An efficient disk-based tool for solving very large markov models'. Together they form a unique fingerprint.

Cite this