Publications
254 results found
Chis T, Harrison PG, 2013, Analysing and Predicting Patient Arrival Times, 28th International Symposium on Computer and Information Sciences (ISCIS), Publisher: SPRINGER, Pages: 77-85, ISSN: 1876-1100
Qiu Z, Harrison PG, 2013, A Model of Speculative Parallel Scheduling in Networks of Unreliable Sensors, 28th International Symposium on Computer and Information Sciences (ISCIS), Publisher: SPRINGER, Pages: 107-116, ISSN: 1876-1100
Harrison PG, Qiu Z, 2013, Performance enhancement by means of task replication, 10th European Performance Engineering Workshop (EPEW2013), Pages: 191-205
Casale G, Harrison PG, 2013, AutoCAT: Automated Product-Form Solution of Stochastic Models, Matrix-Analytic Methods in Stochastic Models, Editors: Latouche, Ramaswami, Sethuraman, Sigman, Squillante, Yao, ISBN: 978-1-4614-4908-9
Harrison PG, 2013, Sojourn time distributions in tandem batch-networks, Pages: 37-39
Harrison PG, Thomas N, 2013, Semi-Product-Form Solution for PEPA Models with Functional Rates, 20th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA 2013), Publisher: Springer, Pages: 416-430
Harrison PG, Qiu Z, 2013, Performance Enhancement by Means of Task Replication., Publisher: Springer, Pages: 191-205
Chis TS, Harrison PG, 2012, Incremental HMM with an improved baum-welch algorithm, Pages: 29-34
There is an increasing demand for systems which handle higher density, additional loads as seen in storage workload modelling, where workloads can be characterized on-line. This paper aims to find a workload model which processes incoming data and then updates its parameters "on-the-fly." Essentially, this will be an incremental hidden Markov model (IncHMM) with an improved Baum-Welch algorithm. Thus, the benefit will be obtaining a parsimonious model which updates its encoded information whenever more real time workload data becomes available. To achieve this model, two new approximations of the Baum-Welch algorithm are defined, followed by training our model using discrete time series. This time series is transformed from a large network trace made up of I/O commands, into a partitioned binned trace, and then filtered through a K-means clustering algorithm to obtain an observation trace. The IncHMM, together with the observation trace, produces the required parameters to form a discrete Markov arrival process (MAP). Finally, we generate our own data trace (using the IncHMM parameters and a random distribution) and statistically compare it to the raw I/O trace, thus validating our model. © Tiberiu S. Chis and Peter G. Harrison.
Jones GL, Harrison PG, 2012, Collecting battery data with open battery, Pages: 75-80
In this paper we present Open Battery, a tool for collecting data on mobile phone battery usage, describe the data we have collected so far and make some observations. We then introduce the fluid queue model which we hope may prove a useful tool in future work to describe mobile phone battery traces. © Gareth L. Jones and Peter G. Harrison.
Harrison PG, Marin A, 2012, Deriving the rate equations characterising product-form models and application to propagating synchronisations, 'VALUETOOLS', IEEE, 2012
Marin A, Balsamo S, Harrison PG, 2012, Analysis of stochastic Petri nets with signals, PERFORMANCE EVALUATION, Vol: 69, Pages: 551-572, ISSN: 0166-5316
- Author Web Link
- Open Access Link
- Cite
- Citations: 19
Jones GL, Harrison PG, Field AJ, et al., 2012, Fluid Queue Models of Renewable Energy Storage, 'VALUETOOLS', IEEE, 2012, Publisher: IEEE, Pages: 224-225
PrintRequest PermissionsIn this extended abstract we introduce an approximation algorithm for the evaluation of networks of fluid queues. Such models can be used to describe the generation and storage of renewable energy. We discuss how our algorithm would be applied to an example where the approximation performs very well, and note a modification to the model which would result in a poorer result.
Balsamo S, Harrison PG, Marin A, 2012, Methodological Construction of Product-Form Stochastic Petri nets for Performance Evaluation, Journal of Systems and Software, Vol: 85
Tsimashenka I, Knottenbelt W, Harrison P, 2012, Controlling variability in split-merge systems, Pages: 165-177, ISSN: 0302-9743
We consider split-merge systems with heterogeneous subtask service times and limited output buffer space in which to hold completed but as yet unmerged subtasks. An important practical problem in such systems is to limit utilisation of the output buffer. This can be achieved by judiciously delaying the processing of subtasks in order to cluster subtask completion times. In this paper we present a methodology to find those deterministic subtask processing delays which minimise any given percentile of the difference in times of appearance of the first and the last subtasks in the output buffer. Technically this is achieved in three main steps: firstly, we define an expression for the distribution of the range of samples drawn from n independent heterogeneous service time distributions. This is a generalisation of the well-known order statistic result for the distribution of the range of n samples taken from the same distribution. Secondly, we extend our model to incorporate deterministic delays applied to the processing of subtasks. Finally, we present an optimisation scheme to find that vector of delays which minimises a given percentile of the range of arrival times of subtasks in the output buffer. A case study illustrates the applicability of our proposed approach. © 2012 Springer-Verlag.
Casale G, Harrison P, 2012, A class of tractable models for run-time performance evaluation, Pages: 63-74
Run-time resource allocation requires the availability of system performance models that are both accurate and inexpensive to solve. We here propose a new methodology for run-time performance evaluation based on a class of closed queueing networks. Compared to exponential product-form models, the proposed queueing networks also support the inclusion of resources having first-come first-served scheduling under non-exponential service times. Motivated by the lack of an exact solution for these networks, we propose a fixedpoint algorithm that approximates performance indexes in linear time and linear space with respect to the number of requests considered in the model. Numerical evaluation shows that, compared to simulation, the proposed models solved by fixed-point iteration have errors of about 1% - 6%, while, on the same test cases, exponential product-form models suffer errors even in excess of 100%. Execution times on commodity hardware are of the order of a few seconds or less, making the proposed methodology practical for runtime decision-making. Copyright 2012 ACM.
Casale G, Harrison PG, Vigliotti MG, 2012, Product-form approximation of queueing networks with phase-type service
Harrison PG, Harrison SK, Patel NM, et al., 2012, Storage workload modelling by hidden Markov models: Application to Flash memory, PERFORMANCE EVALUATION, Vol: 69, Pages: 17-40, ISSN: 0166-5316
- Author Web Link
- Open Access Link
- Cite
- Citations: 5
Casale G, Harrison PG, 2012, A Tractable Class of Performance Models for Run-Time Service Management, ICPE '12 Proceedings of the 3rd ACM/SPEC International Conference on Performance Engineering, Pages: 63-74
Zertal S, Harrison PG, 2011, Investigating Flash memory wear levelling and execution modes, SIMULATION-TRANSACTIONS OF THE SOCIETY FOR MODELING AND SIMULATION INTERNATIONAL, Vol: 87, Pages: 1081-1091, ISSN: 0037-5497
Lladó CM, Harrison PG, 2011, A PMIF with Petri net building blocks, Pages: 103-108
Performance model interchange formats (PMIFs) support the portability of models and sharing of solutions amongst different tools. XML-based interchange formats have been defined for the interchange of queueing network and Petri net models, amongst others, but there is still scope to extend their application to multiple formalisms, in particular beyond queueing networks. We extend an existing PMIF to hybrid models by including a new type of node, called a "building block", defined as a certain class of Petri nets. The synchronisation primitives of these building blocks can be used to specify fork-join systems whilst, under certain conditions, retaining product-form solutions when embedded in queueing (or other) networks possessing this property already. When a product-form does not exist, the whole network is translated into a Petri net and solved either by simulation or direct solution of the underlying Markov chain by an existing analyser. Finally, we apply the extended PMIF to model a computer system with RAID storage.
Harrison PG, Liadó CM, 2011, Hierarchically constructed Petri-nets and product-forms, Pages: 101-110
Stochastic Petri nets (SPNs) provide a convenient, diagrammatic description of concurrent systems, such as computer and communication networks, and can represent quantitative (or performance) aspects such as mean response times and probability of failure. Such models can be supported by performance modelling interchange formats (PMIFs), facilitating sharing and model interoperability. We propose a hierarchical method for constructing a large class of Petri nets, which preserves efficient product-form solutions when they exist. This scalable approach greatly improves the efficiency of finding steady state probabilities in a wide range of SPNs, making much larger SPNs feasible. An existing PMIF is extended by including a new type of node that describes a particular type of small Petri net, called a "building block", the synchronisation primitives for which can be used to specify task-spawning and task-gathering, whilst retaining productform solutions under specified conditions. When there is no product-form, the whole network is translated into a Petri net and solved directly - either by a Markov chain solver or by simulation. The extended PMIF and the proposed methodology are applied to a model of a computer system with RAID storage. Copyright © 2011 ICST.
Jones GL, Harrison PG, Harder U, et al., 2011, Fluid Queue Models of Battery Life, MASCOTS 2011, Pages: 278-285, ISSN: 1526-7539
We investigate how a power-save mode effects the battery life of a device subject to stochastically determined charging and discharging periods. We use a multi-regime fluid queue, imposing a threshold at some value. When the power level falls below the threshold, a power-save mode is entered and the rate of discharge decreased. An expression for the Laplace transform of the battery life's probability density function is found and inverted numerically in particular instances. We show the life of battery can be significantly improved by the introduction of the power saving threshold.
Harrison PG, Thomas N, 2011, Product-Form Solution in PEPA via the Reversed Process, NETWORK PERFORMANCE ENGINEERING: A HANDBOOK ON CONVERGENT MULTI-SERVICE NETWORKS AND NEXT GENERATION INTERNET, Vol: 5233, Pages: 343-356, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 1
Balsamo S, Harrison PG, Marin A, 2010, A unifying approach to product-forms in networks with finite capacity constraints, Performance Evaluation Review, Vol: 38, Pages: 25-35, ISSN: 0163-5999
In queueing networks with blocking, stations wishing to transmit customers to a full queue are blocked and need to take alternative action on completing a service. In general, product-forms, i.e. separable solutions for such a network's equilibrium state probabilities, do not exist but some productforms have been obtained over the years in special cases, using a variety of techniques. We show that the Reversed Compound Agent Theorem (RCAT) can obtain these diverse results in a uniform way by its direct application, so unifying product-forms in networks with and without blocking. New product-forms are also constructed for a type of blocking we call 'skipping', where a blocked station sends its output-customers to the queue after the one causing the blocking in that customer's path. Finally, we investigate a novel congestion management scheme for networks of finite-capacity queues in which a station with a full queue transmits signals that delete customers from upstream queues in order to reduce incoming traffic.
Harrison PG, 2010, Turning Back Time-What Impact on Performance?, COMPUTER JOURNAL, Vol: 53, Pages: 860-868, ISSN: 0010-4620
- Author Web Link
- Open Access Link
- Cite
- Citations: 2
Field AJ, Harrison PG, 2010, BUSY PERIODS IN FLUID QUEUES WITH MULTIPLE EMPTYING INPUT STATES, JOURNAL OF APPLIED PROBABILITY, Vol: 47, Pages: 474-497, ISSN: 0021-9002
- Author Web Link
- Cite
- Citations: 1
Martínez Ortuño F, Harder U, Harrison PG, 2010, A Markovian futures market for computing power, Pages: 177-182
In this paper we describe aspects of a market model for Grid computing. In particular we concentrate on Grid computing provided by a peer-to-peer network architecture. In this network nodes can either buy or sell computing power in exchange for money. Building on previous publications we develop a mathematical market model using Markov chains. The behaviour of each agent in the market is described by a Markov chain of decisions on buying, selling or holding. Considering the contributions of all agents, we calculate the global Markov chain of the market state as a whole, by making use of a concept of market pressure that reduces the state space of the entire market model. We show that the Markov chain model describes the market behaviour seen in a simulation extremely well. In a similar way to other perishable commodity markets like fish and electricity, we also provide a model for trading future contracts on the purchase and sale of computing power in this market. Using Markov Decision Processes we derive an optimal trading strategy. This work introduces a pioneer mathematical model for future global peer-to-peer Grid computing architectures like MaGoG (Middleware for activating the Global open Grid), where we have derived a global transition probability matrix that determines the behaviour of the market by summing up the contributions of different kinds of market participants. © 2009 ACM.
Harrison PG, Patel NM, Zertal S, 2010, Response time distribution of flash memory accesses, PERFORMANCE EVALUATION, Vol: 67, Pages: 248-259, ISSN: 0166-5316
- Author Web Link
- Open Access Link
- Cite
- Citations: 5
Balsamo S, Harrison PG, Marin A, 2010, A unifying approach to product-forms in networks with finite capacity constraints, Sigmetrics 2010, Publisher: ACM, Pages: 25-35
Zertal S, Harrison PG, 2009, Investigating Flash memory wear levelling and execution modes, Pages: 81-88
The impact of wear levelling on a Flash storage package and its access operations' execution modes is investigated. Simple, static logical to physical mapping functions are proposed and their implied wear levelling is assessed for different address distributions, covering both unifrom access and hot spots, as well as the Flash chip utilisation within the whole package. For the access execution modes, different preemptive and non-preemptive priority schemes are considered with a range of IO arrival rates using Poisson, Erlang and Pareto-based arrival processes. The analysis of the impact of the execution modes on the performance of the Flash memory is undertaken using a hardware simulator. The results obtained show clearly the good wear levelling obtained by the mapping functions, even in presence of hot spots and the effect of the chosen execution mode on the whole storage package for each IO workload type.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.