Automatic bottleneck detection by means of workload reconstruction from performance measurements

A system and method for determining a workload placed on a target computer system during execution of a specified computer program. The system receives a set of performance measurements representing the performance of the target computer system during execution of the specified computer program. The system then identifies a plurality of workloads and for each identified workload, uses a model of the target computer system to predict a set of performance measurements that would results when a computer program that places the identified workload on the target computer system is executed. The system selects the identified workload whose set of predicted performance measurements most closely matches the received set of performance measurements as the determined workload that was place on the target computer system during execution of the specified computer program. The system uses the selected workload to predict the performance of the specified computer program on the target computer system with various different configurations. The system also determines the resource that is a bottleneck for each of the different configurations.

TECHNICAL FIELD 
The invention relates generally to the field of computer system performance 
and, more specifically, to identifying changes to computer system 
resources to improve performance. 
BACKGROUND OF THE INVENTION 
Computer system performance has been studied extensively in the field of 
computer science. One goal in studying computer system performance is to 
determine a cost-effective configuration of the computer system that can 
handle the expected workload. The workload placed on a computer system is 
the amount of work to be performed by a computer program and is typically 
specified in terms of resources needed to complete one transaction. For 
example, the workload may specify that the computer program uses five 
seconds of central processor time and performs 10 sequential disk reads 
with an average size of 4096 bytes per transaction. The workload may 
further specify the amount of RAM needed by the application program. To 
predict performance of a computer system when executing a computer program 
with an expected workload, prior techniques have created models of a 
computer system and then apply the expected workload to the model to 
predict performance measurements that would occur when the expected 
workload is placed on the computer system. A performance measurement 
typically corresponds to performance characteristics of a system resource 
(e.g., processor utilization). 
In current computer processing environments, two factors make determining a 
cost-effective configuration using such techniques especially difficult. 
The first factor is the complexity of the interaction between the 
operating system and the hardware. Because of this complexity, it is 
difficult to predict the overall performance of the computer system, and 
thus very difficult to generate an accurate model. For example, although a 
disk drive may be capable of accessing its disk twenty-five times a 
second, the processing performed by the file system may place a further 
limit on the access rate. Moreover, the variety of possible computer 
system configurations, especially with personal computers, makes it 
virtually impossible to generate an accurate model that is appropriate for 
all possible configurations. The second factor is the difficulty in 
determining what is the expected workload. Traditionally, single 
application programs typically executed on dedicated hardware, for 
example, an airline reservation system. With such single application 
systems, it was relatively straightforward to determine the workload 
placed on the computer system. Current computing environments are 
typically client/server-based, and multiple applications may be executing 
on a single computer system. The execution and interaction of the multiple 
applications make it difficult to determine the overall workload. 
Furthermore, it may be difficult to estimate or measure typical patterns 
of usages of the various application programs. 
If, however, an appropriate model could be developed and an accurate 
workload could be specified, then it may be possible to identify the 
system resources that are a "bottleneck." A bottleneck is the computer 
system resource that has the highest utilization during execution of a 
workload. (Although it is possible to have multiple bottlenecks, that is, 
resources with the same highest utilization, such occurrences are rare.) 
For example, if a workload requires 0.25 seconds of CPU time per 
transaction and 0.5 seconds of disk time per transaction, then the disk is 
a bottleneck because its 50% utilization is greater than the processor's 
25% utilization. In other words, the disk can handle 2 transactions per 
second and the CPU can handle 4 transactions per second. Thus, if the 
current CPU was replaced by a CPU that was twice as fast, the computer 
system still could only handle 2 transactions per second. Conversely, if 
the current disk drive, the bottleneck, is replaced by a disk drive that 
is twice as fast, then the computer system could handle 4 transactions per 
second. Once a particular resource is identified as a bottleneck, a number 
of remedies exist. These include distributing the load on the resource 
across additional instances of that resource, installing a faster 
resource, or redesigning the workload to use another resource. These 
remedies will resolve the bottleneck by reducing the time spent using the 
bottleneck resource. Bottlenecks cannot be eliminated, however, only 
moved. There is always some resource which can be faster to the benefit of 
the workload's completion time. Thus, the decision to remove a bottleneck 
is frequently an issue of cost versus benefit. 
SUMMARY OF THE INVENTION 
The present invention provides system and method for determining a workload 
placed on a target computer system during execution of a specified 
computer program. The system receives a set of performance measurements 
representing the performance of the target computer system during 
execution of the specified computer program. The system then identifies a 
plurality of workloads and for each identified workload, predicts a set of 
performance measurements that would results when a computer program that 
places the identified workload on the target computer system is executed. 
The system selects the identified workload whose set of predicted 
performance measurements most closely matches the received set of 
performance measurements as the determined workload that was place on the 
target computer system during execution of the specified computer program. 
In one aspect of the present invention, the system generates an analysis of 
modifications to a system resource of a target computer system that would 
result in improved performance during execution of computer programs on 
the target computer system. The system first collects performance 
characteristics of system resources of the target computer system and 
collects a set of actual performance measurements of the target computer 
system during execution of the computer programs on the target computer 
system. For each of the plurality of the test workloads, the system 
generates a set of predicted performance measurements that would result 
when the test workload is placed on the target computer system based on 
the collected performance characteristics of the target computer system. 
The system then determines the set of predicted performance measurements 
that most closely matches the set of actual performance measurements, such 
that the test workload when placed on the target computer system would 
result in the determined set of predicted performance measurements is the 
workload that most probably represents the actual workload. The system 
then identifies a system resource that is a bottleneck during execution of 
the computer programs based on the set of predicted performance 
measurements that most closely matches the set of actual performance 
measurements and selects a system resource that can be modified to reduce 
utilization of the bottleneck system resource. Finally, the system 
generates a set of predicted performance measurements that would result 
when the test workload that most probably represents the actual workload 
placed on the target computer system based on the collected performance 
characteristics of the target computer system with the selected system 
resource modified to reduce utilization of the bottleneck system resource. 
These and other aspects of the present invention are more fully described 
below.

DETAILED DESCRIPTION OF THE INVENTION 
The present invention provides a method and a system for determining a 
cost-effective configuration for a target computer system that executes a 
set of target computer programs. To determine the configuration, the 
system collects actual performance measurements from the target computer 
system as it executes the target computer programs. The system uses these 
actual performance measurements along with a model of the target computer 
system to determine the most likely (or most probable) workload placed on 
the target computer system by the target computer program. In this way, an 
estimate of the actual workload can be generated. The system then uses the 
most probable workload to determine which system resource is the 
bottleneck resource. In a preferred embodiment the system provides an 
analysis of possible changes to the target computer system's configuration 
that will result in improved performance. 
To determine a most probable workload, the system uses a model of a 
computer system and the actual performance measurements that were 
collected during execution of the target computer program. In the 
preferred embodiment, the model is a set of equations that predict what 
various performance measurements would be if a specified workload were 
placed on the computer system. To generate the predicted performance 
measurements, the set of equations interrelates the performance 
characteristics of the target computer system with the most probable 
workload. Although the preferred embodiment uses a model known as an 
"atomic model," the present invention can be used in conjunction with 
various other modeling techniques, such as, queuing theory and simulation 
techniques. 
Before determining the most probable workload, the system determines the 
performance characteristics of individual resources of the target computer 
system. These performance characteristics are input to the model to 
effectively adapt the model to the target computer system. The system 
determines the performance characteristics (e.g., disk drive maximum 
transfer rate) of the various resources by placing various workloads, 
designed to determine the maximum performance of the resource, on the 
target computer system. For example, a workload that simply writes a 1K 
block to the disk per transaction is used to determine the maximum 
transfer rate to disk when the block size is 1K. This workload is placed 
on the target computer system for a certain period of time (e.g., 10 
seconds) when no other workload is placed on the target computer system, 
and the number of bytes transferred is divided by the time period to 
arrive at the maximum transfer rate. 
After the performance characteristics are determined, the system performs 
an error analysis of the adapted model. To generate the error analysis, 
the system applies a series of workloads to the adapted model to generate 
predicted performance measurements and executes a computer program that 
places the same series of workloads on the target computer system to 
generate actual performance measurements. The system uses the differences 
in the predicted performance measurements (from the model) and the actual 
performance measurements as a representation of the error in the adapted 
model. 
After the performance characteristics have been determined and the error 
analysis completed, the model is ready for use in determining the most 
probable workload for a set of actual performance measurements. The 
adapted model is used to search for the workload that when placed on the 
target computer system is most likely based on the actual performance 
measurements collected during execution of the target computer program. 
Starting with an initial workload, the system applies the workload to the 
model to predict a set of performance measurements for the initial 
workload and then generates a probability that the workload generated the 
actual performance measurements. The system then generates a second 
workload by changing one or more workload parameters. The system then 
applies the second workload to the model to predict a second set of 
performance measurements and generates a second probability. As the system 
iterates, it seeks workloads that result in ever higher probability. In 
general, the system uses numerical search techniques to seek the workload 
which minimizes the probabilistic difference between the predicted 
performance measurements and the actual performance measurements in light 
of the error analysis. The resulting workload is called the most probable 
workload. 
Once the most probable workload is determined, the adapted model is used to 
predict the resulting performance of various changes to the configuration 
of the target computer system. A user inputs to the system a range of 
possible configuration changes, including their performance 
characteristics and their costs. Using the model, the most probable 
workload, and the new performance characteristics, the system then 
predicts the new performance measurements. The system then displays the 
resulting price/performance choices to the user. 
Target Computer System 
FIG. 1 is a block diagram illustrating the target computer system. The 
target computer system comprises an operating system 101, and computer 
system hardware resources 102a-102b. The operating system further includes 
an application programming interface (API) 101a and a kernel 101b. In 
operation, the application programs 103a-103b place a workload on the 
target computer system by invoking functions of the API. The functions 
invoke the services of the kernel to access the various hardware resources 
of the computer system. 
The System 
FIG. 2 is a block diagram illustrating components of the system in a 
preferred embodiment. The system comprises the model 220 and the system 
routines 230 and uses the pre-existing components 210. The pre-existing 
components include the operating system 211, which outputs actual 
performance measurements 212 during execution of workload, and the 
synthetic workload generator 213, which effects the placing of the 
workload 214 on the target computer system. The model 220 comprises the 
Operating System (O.S.) Performance Table 221, the Hardware/Software (H/S) 
Installed Table 222, the Hardware Performance Table 223, a Workload Table 
224, equations 225, and predicted performance measurements 226. The system 
routines 230 include the determine performance routine 231, the determine 
error routine 232, the determine most probable workload routine 233, the 
generate configuration analysis routine 234, and the Hardware Available 
Table 235. 
In operation, the determine performance routine is initially executed to 
determine the performance characteristics of the system resources and to 
store the performance characteristics in the Hardware Performance Table. 
The determine performance routine specifies various workloads and uses the 
synthetic workload generator to place the specified workloads on the 
target computer system. The determine error routine specifies various 
error analysis workloads and uses the synthetic workload generator to 
generate the actual performance measurements for the error analysis 
workloads. The determine error routine also applies those workloads to the 
model to generate predicted performance measurements. The determine most 
probable workload routine repeatedly specifies test workloads and applies 
the test workloads to the model to generate predicted performance 
measurements. The predicted performance measurements are compared to the 
actual performance measurements in light of the error analysis. The test 
workload that resulted in the predicted performance measurements that are 
closest to the actual performance measurements is selected as the most 
probable workload. The generate configuration analysis routine adjusts the 
Hardware Performance Table based on the Hardware Available Table and then 
applies the most probable workload to the model to determine the effect of 
changes in the configuration of the target computer system. 
The Model 
FIG. 3 is a diagram illustrating a portion of a preferred model of a 
computer system. The model inputs an Operating System (O.S.) Performance 
Table, a Hardware/Software (H/S) Installed Table, a Hardware Performance 
Table, and a workload, and outputs the predicted performance measurements 
that would result from applying the input to the model. The model uses 
various equations to combine the input to generate predicted performance 
measurements. Squares 301a-301g represent operating system performance 
characteristics from the O.S. Performance Table. Hexagons 302a-302d 
represent installed hardware and software characteristics from the H/S 
Installed Table Octagons 303a-303b represent hardware performance 
characteristics from the Hardware Performance Table. Triangles 304a-304b 
represent parameters of the workload. Circles 305a-305o and star 306 
represent the equations of the model. Star 306 also represents a 
performance measurement that is predicted by the model. For example, the 
equation for "thrashing level" as represented by circle 305e is 
##EQU1## 
That is, the thrashing level is a function of the amount of installed RAM 
represented by hexagon 302b and the combined RAM demand of the workload 
and the operating system represented by circle 305d. Table 1 contains a 
listing of the equations corresponding to the portion of the model shown 
in FIG. 3. The model described is based on the Microsoft Windows NT 
Operating System executing on an Intel 80486-based computer system. 
TABLE 1 
__________________________________________________________________________ 
// The following are NT characteristics or can be measured directly. 
System.sub.-- Paged: 
["megabytes"] 
CSRSS.sub.-- RAM.sub.-- Demand + 
Spooler.sub.-- RAM.sub.-- Demand + 
Pool.sub.-- Paged + 
System.sub.-- Code.sub.-- Paged + 
System.sub.-- Nominal.sub.-- Available.sub.-- Bytes 
System.sub.-- Non.sub.-- Paged: 
["megabytes"] 
Pool.sub.-- Non.sub.-- Paged + 
Kernel.sub.-- Non.sub.-- Paged + 
Protocol.sub.-- Non.sub.-- Paged + 
Drivers.sub.-- Non.sub.-- Paged + 
// Relative.sub.-- Memory.sub.-- Size is a property of installed 
processor type. 
Relative.sub.-- Memory.sub.-- Usage: 
["ratio"] 
Index(Relative.sub.-- Memory.sub.-- Size, 
Installed.sub.-- Processor.sub.-- Index - 1) 
RAM.sub.-- Demand: 
["megabytes"] 
( 
Relative.sub.-- Memory.sub.-- Usage * 
( 
System.sub.-- Non.sub.-- Paged + System.sub.-- Paged 
) 
) + 
APPLICATION.sub.-- RAM.sub.-- DEMAND 
// This is the key formula for mapping system RAM requirements. 
Thrashing.sub.-- Level: 
["fraction from 0 to 1"] 
1/ 
( 
( 
1 + 
exp 
( 
min 
( 
500, 
(Installed.sub.-- RAM - RAM.sub.-- Demand) 3 
) 
) 
) 
) 
// These formulae determine input page cluster size. 
System.sub.-- Page.sub.-- Input.sub.-- Size: 
["bytes"] 
max 
( 
Page.sub.-- Size.sub.-- Used, 
2.5 * Page.sub.-- Size.sub.-- Used * Thrashing.sub.-- 
Level 
) 
System.sub.-- Page.sub.-- Input.sub.-- Cluster: 
["bytes"] 
Page.sub.-- Size.sub.-- Used * 
( 
int 
( 
( System.sub.-- Page.sub.-- Input.sub.-- Size + 
Page.sub.-- Size.sub.-- Input) / Page.sub.-- 
Size.sub.-- Used 
) 
) 
// This formula determines maximum paging rate. 
Input.sub.-- Paging.sub.-- Disk.sub.-- Throughput: 
["bytes/second"] 
Hlookup(System.sub.-- Page.sub.-- Input.sub.-- Cluster, 
Random.sub.-- Disk.sub.-- Throughput, 
Paging.sub.-- Disk.sub.-- Index, 
FALSE) 
// These formulae determine actual input page rate. 
Disk.sub.-- Paging.sub.-- Demand: 
["Fraction from 0 to 1"] 
LOCAL.sub.-- PAGING.sub.-- AFFINITY * 
Thrashing.sub.-- Level 
Disk.sub.-- Paging.sub.-- Read.sub.-- Rate: 
["operations/second"] 
Disk.sub.-- Paging.sub.-- Demand * 
( 
Input.sub.-- Paging.sub.-- Disk.sub.-- Throughput / 
System.sub.-- Page.sub.-- Input.sub.-- Size 
) 
Disk.sub.-- Page.sub.-- Input.sub.-- Rate: 
["pages/sec"] 
Disk.sub.-- Paging.sub.-- Read.sub.-- Rate * 
System.sub.-- Page.sub.-- Input.sub.-- Size / 
Page.sub.-- Size.sub.-- Used 
Input.sub.-- Page.sub.-- Rate: 
["pages/sec"] 
Disk.sub.-- Page.sub.-- Input.sub.-- Rate + 
Net.sub.-- Page.sub.-- Input.sub.-- Rate 
Memory Pages.sub.-- Input.sub.-- Per.sub.-- Sec: 
["pages/second"] 
Input.sub.-- Page.sub.-- Rate + 
( 
( 
Disk.sub.-- Read.sub.-- Rile.sub.-- Byte.sub.-- Rate + 
Net.sub.-- Read.sub.-- File.sub.-- Byte.sub.-- Rate 
) / 
Page.sub.-- Size.sub.-- Used 
) 
__________________________________________________________________________ 
FIGS. 4, 5, and 6 illustrate the tables that are input to the equations of 
model. Each of these tables are represented in a spreadsheet format. The 
row of the tables are identified by numbers and the columns are identified 
by letters. Each cell in the table contains either a formula or a value. 
The formulae use standard spreadsheet conventions. FIG. 4A represents the 
O.S. Performance Table. The O.S. Performance Table is stored in the 
spreadsheet named "software.xls" and contains entries for various 
operating system characteristics. Each entry contains the name of the 
operating system characteristic and a value or formula for calculating a 
value. For example, one entry row 34 contains the name "Spooler.sub.-- 
RAM.sub.-- Demand," and a value of "1.2." This entry represents the amount 
of RAM (in mega bytes) that is required by the spooler of the operating 
system. Another entry row 13 contains the name "System.sub.-- 
Sequential.sub.-- Write.sub.-- Cache.sub.-- Processing" and the formula 
EQU =0.0001914+0.000000099653*app.xls'!APPLICATION.SEQUENTIAL.sub.-- 
WRITE.sub.-- SIZE 
This formula indicates that the amount of CPU time the operating system 
spends processing each sequential write using the file system cache is the 
constant "0.0001914" seconds plus "0.000000099653" seconds per byte times 
the sequential write size. As shown, the sequential write size is 
dependent on the workload being applied to the model. The term 
"app.xls'!APPLICATION.SEQUENTIAL.sub.-- WRITE.sub.-- SIZE" refers to the 
workload parameter stored in the cell identified as "APPLICATION.sub.-- 
SEQUENTIAL.sub.-- WRITE.sub.-- SIZE" in the "app.xls" spreadsheet. 
This information about the performance of the operating system is 
preferably generated during the construction of the model by using the 
synthetic workload generator to apply known workloads to a baseline 
computer system and using the actual performance measurements as an 
indication of the operating system performance. FIG. 4B contains the names 
of the cells in the O.S. Performance Table. For example, the cell B33 is 
named "CSRSS.sub.-- RAM.sub.-- Demand." These cell names are used by the 
equations of the model to specify the source of the parameters of the 
equations. 
FIG. 5A represents the H/S Installed Table. The H/S Installed Table is 
stored in the spreadsheet named "hardware.xls" and contains entries 
indicating the installed configuration of the target computer system. For 
example, entry row 14 contains the name "Installed.sub.-- RAM" and the 
value "16." This entry represents the amount of RAM installed on the 
target computer system in mega bytes. Information in this table is 
obtained from the Operating System; in the case of Windows NT this 
information is retrieved from a database called the Configuration Registry 
which Windows NT constructs when it is installed on the target computer 
system. FIG. 5B contains the names the cells of the H/S Installed Table. 
FIGS. 6A-6K represent the Hardware Performance Table. The Hardware 
Performance Table is stored in the spreadsheet named "hardware.xls" and 
contains entries indicating various performance characteristics of the 
target computer system. This information is preferably generated when the 
system is initially loaded on the target computer system. In addition, the 
information is regenerated whenever the hardware resource is changed 
(e.g., a faster disk drive installed). Table 2 contains a listing of the 
performance characteristics. 
TABLE 2 
__________________________________________________________________________ 
PERFORMANCE 
CHARACTERISTICS 
DEFINITIONS 
__________________________________________________________________________ 
Processor Page Size 
The page size in bytes used by the processor. 
Relative Memory Usage 
The amount of memory used by a computer program relative to 
the 
amount of a baseline processor (e.g, Intel 80486). 
Relative Processor Speed 
The speed of the processor relative to a baseline 
processor. 
Disk Controller Speed 
The transfer speed in bytes of the disk controller. 
Base Disk Controller 
The base CPU time in seconds used by the operating system 
to 
Processing Overhead 
process a sequential disk transfer. 
Sequential 
Base Disk Controller 
The base CPU time in seconds used by the operating system 
to 
Processing Overhead Random 
process a random disk transfer. 
Incremental Disk Controller 
The incremental CPU time in seconds used by the operating 
system 
Processing Overhead 
to process each byte in a sequential disk transfer. 
Sequential 
Incremental Disk Controller 
The incremental CPU time in seconds used by the operating 
system 
Processing Overhead Random 
to process each byte in a random disk transfer. 
Random Disk Throughput [ ] 
The maximum transfer rate for a random access transfer to 
disk for 
various block sizes. 
Sequential Disk Throughput 
The maximum transfer rate for a sequential access transfer 
to disk 
[ ] for various block sizes. 
Network Speed 
The transfer speed of the network in bytes per second. 
Network Adapter Speed [ ] 
The transfer speed of the network adapter in bytes per 
second for 
various block sizes. 
__________________________________________________________________________ 
The performance characteristics followed by brackets correspond to an array 
of characteristics collected using various block sizes (e.g., 1K and 4K). 
In one embodiment, the performance characteristics for various 
configurations are collected and stored in a database. That is, rather 
than determining the performance characteristics dynamically on the target 
computer system, they are collected once and stored in a database. FIGS. 
6A-6K represent such a database. The Hardware Performance Table contains 
the following sub-tables. The dynamic determination of the performance 
characteristic is preferable to such a database. 
1. Processor Architecture (FIG. 6A) 
2. Processor Family (FIG. 6B) 
3. Processor Speed (FIG. 6C) 
4. Disk Controller Architecture (FIG. 6D) 
5. Base Disk Controller Processing Overhead (FIG. 6E) 
6. Incremental Disk Controller Processing Overhead (FIG. 6F) 
7. Random Disk Throughput (FIG. 6G) 
8. Sequential Disk Throughput (FIG. 6H) 
9. Network Type (FIG. 6I) 
10. Network Adapter (FIG. 6J) 
11. Graphics Controller Speed (FIG. 6K) 
FIG. 6A represents the Processor Architecture Table. This table contains 
page size and relative memory size. The page size is the size in bytes 
used by the paging system (e.g, 4096 bytes for the Intel 80486 
architecture). The relative memory size is the amount of memory that a 
computer program occupies relative to the Intel 80486 architecture. For 
example, since the Intel 80486 uses a complex instruction set architecture 
and the DEC Alpha processor uses a reduced instruction set architecture, 
computer programs for the DEC Alpha processor are approximately 1.744251 
times as large as the corresponding computer program for the Intel 80486 
processor. This performance characteristic is determined when the model is 
constructed by comparing the amount of memory occupied by the Windows NT 
operating system on each architecture. 
FIG. 6B represents the Processor Family Table. This table is used to 
retrieve an index into the Processor Speed Table based on the processor 
architecture and speed. FIG. 6C represents the Processor Speed Table. The 
Processor Speed Table contains an entry for each processor and secondary 
cache size. The speeds in the table are relative to the speed of the Intel 
80486D0-50/2 processor. The processor speed can be determined dynamically 
by timing various known workloads. 
FIG. 6D represents the Disk Controller Architecture Table. This table 
contains the transfer rate of various disk controllers in bytes per 
second. FIG. 6E represents the Base Disk Controller Processing Overhead 
Table. This table contains the overhead in seconds of the operating system 
per access of the disk. FIG. 6F represents the Incremental Disk Controller 
Processing Overhead Table. This table contains the incremental overhead in 
seconds of the operating system that each byte adds to a disk access. FIG. 
6G represents the Random Disk Throughput Table. This table contains the 
maximum number of bytes per second that can be transferred for various 
block sizes via random access transfer. FIG. 6H represents the Sequential 
Disk Throughput Table. This table contains the maximum number of bytes per 
second that can be transferred for various block sizes via sequential 
access transfer. FIG. 6I represents the Network Table. This table contains 
the maximum network transfer rate in bytes per second. FIG. 6J represents 
the Network Adapter Table. This table contains the maximum number of bytes 
that can be transferred by the network adapter per second with various 
block sizes. FIG. 6K represents the Graphics Controller Speed. This table 
represents the time to transfer one pixel to the graphics controller. 
Synthetic Workload Generator 
The synthetic workload generator is a computer program that receives a 
description of a workload (a set of workload parameters) and places a 
workload that corresponds to the parameters on the target computer system. 
A preferred synthetic workload generator is described in Blake, R. 
"Optimizing Windows NT," Vol. 4, Appendix C, Microsoft Press, 1993, or 
described in "Tuning an Operating System for General Purpose Use," 
Computer Performance Evaluation, The Chameleon Press Ltd., London, Sep. 
1976, pp. 303-322. A synthetic workload generator receives a certain 
workload description, and effects the execution of that workload on the 
target computer system. A workload description is a set of parameters that 
specify a load on the computer system. For example, the parameters may 
specify the maximum amount of RAM required by the workload, average 
processor time needed between sequential reads of the disk, and the 
average size of each read. Table 3 contains a list of the preferred 
workload parameters. 
TABLE 3 
__________________________________________________________________________ 
WORKLOAD AMETER 
DEFINITION 
__________________________________________________________________________ 
Code RAM Demand 
The average amount of RAM used by the workload code. 
Data RAM Demand 
The average amount of RAM used by the workload data. 
Local Paging Affinity 
The fraction of paging on local disks, as opposed to on the 
network. 
Sequential Read Processing 
The amount of application processor time on the baseline 
system between sequential reads of disk or network. 
Sequential Write Processing 
The amount of application processor time on the baseline 
system between sequential writes to disk or network. 
Random Read Processing 
The amount of application processor time on the baseline 
system between random access reads from disk or network. 
Random Write Processing 
The amount of application processor time on the baseline 
system between random access writes to disk or network. 
Sequential Read Size 
The size of each sequential read from disk. 
Sequential Write Size 
The size of each sequential write to disk. 
Random Read Size 
The size of each random access read from disk. 
Random Write Size 
The size of each random access write to disk. 
Local Sequential Read 
The fraction of sequential reads to local disk, as opposed 
to the 
Affinity network. 
Local Sequential Write 
The fraction of sequential writes to local disk, as opposed 
to 
Affinity the network. 
Local Random Read Affinity 
The fraction of random reads to local disk, as opposed to 
the 
network. 
Local Random Write 
The fraction of random writes to local disk, as opposed to 
the 
Affinity network. 
Random Read Extent 
The size of the portion of the disk being randomly read. 
Random Write Extent 
The size of the portion of the disk being randomly 
__________________________________________________________________________ 
written. 
Performance Measurements 
Operating systems typically record various actual performance measurements 
during execution of application programs. The performance measurements may 
include average number of pages of virtual memory transferred to and from 
main memory per second and average number of bytes per second transferred 
to and from the disk. The system uses the model to predict various 
performance measurements. Table 4 contains a list of performance 
measurements that are generated by the target computer system and that are 
predicted by applying a workload to the model. These performance 
measurements are described in detail in Blake, R., "Optimizing Windows 
NT," Vol. 4, Appendix A, Microsoft Press, 1993. 
TABLE 4 
______________________________________ 
PERFORMANCE MEASUREMENT 
DEFINITION 
______________________________________ 
System.PctPriv Percent of time the processor 
is in privileged mode. 
System.PctUser Percent of time the processor 
is in user mode. 
System.SystemCallRate 
Average number of calls per 
second to the system service 
routines that perform basic 
scheduling and synchronization 
of activities of the computer and 
that provide access to non- 
graphical devices, memory 
management, and name space 
management. 
Disk.DiskReadByteRate 
Average number of bytes per 
second that are transferred from 
the disk during a read operation. 
Disk.DiskReadRate Average number of disk read 
operations per second. 
Disk.DiskWriteByteRate 
Average number of bytes per 
second that are transferred from 
the disk during a write 
operation. 
Disk.DiskWriteRate Average number of disk write 
operations per second. 
Cache.CopyReadHitsPct 
Percentage of file read 
operations that are satisfied by a 
memory copy from cache. 
Cache.CopyReadsPerSec 
The number of file read 
operations per second that are 
satisfied by a memory copy from 
the cache. 
Cache.LazyWritePagesPerSec 
The number of writes per 
second to update the disk to 
reflect changes stored in 
the cache. 
Memory.PageFaultsPerSec 
Average number of page faults 
per second. A page fault 
occurs when a process refers 
to a virtual memory page that is 
not in main memory. 
Memory.CacheFaultsPerSec 
Average number of cache 
faults per second. A cache fault 
occurs when the page of a file is 
not found in the cache. 
Memory.PagesInputPerSec 
Average number of pages read 
from disk per second to 
resolve memory references to 
pages not in memory at the 
time of the reference. 
Memory.PagesOutputPerSec 
Average number of pages 
written to disk per second 
because the page in memory 
was modified. 
______________________________________ 
Equations 
FIGS. 7-1 through 7-17 list the equations of the preferred model. The 
equations input the spreadsheets "software.xls," "install.xls," 
"hardware.xls," and "app.xls," which correspond to the O.S. Performance 
Table, the H/S Install Table, and the Hardware Performance Table, and the 
Workload Table, respectively. The equations generate the predicted 
performance measurements. FIG. 8 contains a mapping from the names used in 
the equations of the model to the cells in the tables from which the data 
is retrieved. 
Detailed Description of the System 
FIG. 9 is a flow diagram of a preferred implementation of the system. The 
system adapts the model to the target computer system and then collects 
actual performance measurements during execution of a target computer 
program, identifies a workload that when placed on the target computer 
system would generate the actual performance measurements, and generates 
an analysis of changes to the configuration of the target computer system. 
In step 901, the system adapts the model of the computer system to the 
target computer system. The model models a baseline computer system, such 
as, IBM compatible personal computer with an Intel 80486 DX/250 processor 
and 16M bytes of RAM and that executes the Microsoft Windows NT Operating 
System. The adaptation of the model typically occurs once for the target 
computer system. The adapting of the model involves determining the 
performance characteristics of the current computer system. The system 
also generates an error analysis between predicted performance 
measurements generated by the adapted model and actual performance 
measurements. In step 902, the system collects a set of actual performance 
measurements. The actual performance measurements represent performance 
measurements generated by the operating system on the target computer 
system during execution of the target computer program. In step 903, the 
system determines the workload that when placed on the target computer 
system generates performance measurements that most likely match the 
actual performance measurements. To determine the workload, the system 
selects various possible workloads and generates the predicted performance 
measurements for each workload using the adapted model. The workload whose 
predicted performance measurements most closely match the actual 
performance measurements is selected as the most probable workload. In 
step 904, the system selects the computer system resource that is the 
bottleneck. In step 905, the system generates an analysis of configuration 
changes directed to alleviating the bottleneck. The system uses this 
analysis to make a recommendation of the most cost-effective hardware 
improvement for the observed performance problem, and predicts the amount 
of performance improvement expected when that change to the configuration 
is implemented. The recommendation to improve the performance is not 
always as simple as replacing the resource that is the bottleneck with a 
faster resource. For example, the disk drive may be the bottleneck. In 
such a case, the bottleneck may be caused by a large workload of file 
activity. Conversely, the bottleneck may be caused by a large amount of 
virtual memory paging. If the bottleneck is caused by virtual memory 
paging, then the recommendation may be to add more RAM, rather than 
installing a faster disk drive. Also, the recommendation may also be to 
add more RAM even if the bottleneck is caused by file activity. In such a 
case, by increasing the RAM cache of the file system, the utilization of 
the disk drive may be reduced. Consequently, knowledge of the most 
probable workload is important for determining how to alleviate a 
bottleneck. The system is then ready to perform an analysis of the next 
actual workload. 
FIG. 10 is a flow diagram of the process of adapting of the model. The 
process collects the performance characteristics of the target computer 
system and performs an error analysis of the model that is adapted to use 
the collected performance characteristics. In step 1001, the process 
collects various hardware and software configuration information and 
stores the information in the H/S Installed Table. In step 1002, the 
process retrieves the pre-determined operating system performance 
characteristics from the O.S. Performance Table based on the configuration 
information. In step 1003, the process determines the performance 
characteristics of the system resources and stores the results in the 
Hardware Performance Table. The adapted model is the model that uses the 
information in the O.S. Performance Table, the H/S Installed Table, and 
the Hardware Performance Table to generate the predicted performance 
measurements. In step 1004, the process determines the error between 
predicted performance measurements for the calibrated model and actual 
performance measurements for various workloads. In step 1005, the process 
generates an analysis of the errors and returns. 
In a preferred embodiment, the error analysis generates covariance matrix 
based on the actual and predicted performance measurements. Equation (1) 
represents the error between the actual performance measurements (c.act) 
and the predicted performance measurements (c.pre). The actual and 
predicted performance measurements are each represented by an m-by-n 
matrix, where each row represents the performance measurements for one 
workload and each column represents a performance characteristic that is 
measured (m (indexed by i) represents the number of workloads tested and n 
(indexed by i) represents the number of performance characteristics that 
are measured). 
EQU E.sub.i,j =c.act.sub.i,j -c.pre.sub.i,j (1) 
The matrix E represents the difference between each predicted performance 
measurement and each actual performance measurement for each workload 
tested. The process then calculates the average error for each performance 
measurement as shown by equation (2). 
##EQU2## 
The array E.avg represents the average error for each performance 
characteristic. The process then calculates an n-by-n covariance matrix 
Cov of the average error as shown by equation (3). 
##EQU3## 
The resulting covariance matrix is later used to account for the influence 
of the various errors in performance measurements on each performance 
characteristic. Thus, the matrix Cov.sub.k,l represents the error in the 
performance measurements for performance characteristic k combined with 
the error in performance measurements for performance characteristic l. 
They are later taken together to scale the importance of observed 
differences between actual and predicted performance measurements. 
FIG. 11 is a flow diagram of the process of determining the prformance 
characteristics of the system resources. This process generates a variety 
of workloads that are used to determine the throughput of the various 
system resources. Each hardware device has a device-specific subset of the 
workload parameters that can be varied to alter the performance of the 
device. For example, the workload parameters that would alter the 
performance of a disk drive would include sequential and random read and 
write sizes, while the workload parameter that would alter the performance 
of a CD-ROM (Read Only Memory) include read but not write sizes. The 
synthetic workload generator is preferably designed so that the parameters 
for a particular device are independent. That is, the parameters can be 
varied independently and still produce an accurate measure of device 
performance. The process selects the workload parameters for determining 
the performance characteristics by first selecting a device to measure. 
The process then selects a base workload that includes a typical value for 
each parameter for this device. The process then selects the next 
parameter to vary from the subset of parameters that influence the 
performance of this device, and varies this parameter while holding all 
other parameters at their typical values. The process repeats this for 
each parameter value. 
In step 1100, the process selects the next device to measure. In step 1101, 
the process selects the next workload. In step 1102, the process selects 
the next workload parameter for the selected workload. In step 1103 the 
process selects the next workload value for the selected workload 
parameter. In step 1105, the process places the selected workload with the 
selected value for the selected workload parameter on the target computer 
system. In step 1106, the process stores the actual performance 
measurements resulting from the selected workload. In step 1107, if there 
are more values for the selected workload parameter, then the process 
loops to step 1103 to select the next value, else the process continues at 
step 1108. In step 1108, the process optimally replaces the stored 
performance measurements for the selected workload for the selected 
workload parameter with a function (e.g., curve fitting) to more compactly 
represent the performance measurements. In step 1109, if more workload 
parameters are to be varied, then the process loops to step 1102 to select 
the next workload parameter, else the process continues at step 1110. In 
step 1110, if there is another workload for this device, the process loops 
to step 1101 to select the next workload, otherwise the process proceeds 
to step 1111. In step 1111, if all the devices have already been measured, 
then the process returns, else the process loops to step 1100 to select 
the next device. 
FIG. 12 is flow diagram of the process of determining the error in the 
adapted model. The process generates various error analysis workloads and 
then generates predicted performance measurements from the adapted model 
and generates actual performance measurements for the workloads. The 
differences between the predicted and actual performance measurements are 
stored as errors. (The result of this process is stored in the matrix 
Cov.sub.k,i j as discussed above.) In step 1201, the process selects the 
next workload to be analyzed. The process can select the workloads to be 
analyzed in various ways. For example, the process can select workloads 
that represent an even distribution of the workload parameter values, that 
represent a uniform distribution of the workload parameter values, or as 
in the preferred embodiment that represent a distribution based on typical 
workload parameters values. In step 1202, the process places the selected 
workload on the target computer system. In step 1203, the process saves 
the actual performance measurements for the selected workload. In step 
1204, the process applies the selected workload to the adapted model. In 
step 1205, the process stores the predicted performance measurements for 
the selected workload. In step 1206, the process stores the differences 
between the actual performance measurements and the predicted performance 
measurements. In step 1207, if there are more workloads to analyze, then 
the process loops to step 1201 to select the next workload, else the 
process returns. 
FIG. 13 is a flow diagram of the process for determining the most probable 
workload. In steps 1301-1305, the process loops selecting a test workload 
and generates the predicted performance measurements of each selected 
workload. In step 1301, the process selects the next workload. A variety 
of numerical methods can be used for searching the space of all possible 
workloads for the most probable workload. The book "Numerical Recipes in 
C-The Art of Scientific Computing," William Press et al., Cambridge 
University Press, 1988, contains a survey of these techniques in Chapter 
10, Newton's method and the downhill simplex method are examples of such 
numerical search techniques that can be used to select the next workload. 
In the preferred embodiment, Newton's method is used because it is both 
rapid and accurate in this application. In step 1302, the process applies 
the selected workload to the adapted model to generate the predicted 
performance measurements. In step 1303, the process stores the predicted 
performance measurements. In step 1304, the process calculates the 
probability that the selected workload matches the actual workload placed 
on the target computer system by the target computer program. In step 
1305, if all the workloads have already been selected, then the process 
continues at step 1306, else the process loops to step 1301 to select the 
next workload. In step 1306, the process selects the workload with highest 
probability as the most probable workload and returns. 
The system preferably uses one of two methods for determining the 
probability that the generated workload matches the actual workload. The 
first method is the deterministic method. The deterministic method uses a 
numerical analysis, such as a least-squares method, based on the actual 
and predicted performance measurements. That is, the generated workload 
whose predicted performance measurements are closest to the actual 
performance measurements is selected as the most probable workload. The 
following formula is a preferred deterministic method. 
##EQU4## 
The factor .alpha..sub.j is an array of weighting factors to compensate 
for differences in the units of the performance measurements. 
The second method is a probabilistic method. The probabilistic method uses 
an error analysis of the adapted model combined with the probability that 
a given workload will occur based on a historical distribution. (The 
deterministic method is simply a special instance of the probabilistic 
method in which it is assumed that in the adapted model has no correlated 
errors (Cov.sub.ij =0, i not equal to j) and that the historical or prior 
probability for each value of a workload parameter is equal.) The 
probability (Pr) of a workload (.omega.) given we know the actual workload 
is proportional to two other probabilities given by equation (4). 
EQU Pr(.omega..vertline.c.act)=k Pr(c.act.vertline.c.pre)*Pr(.omega.)(4) 
The factor Pr(c.act.vertline.c.pre) represents the probability that the 
actual performance measurements are observed, given generated predicted 
performance measurements. The factor Pr(.omega.) represents the 
probability that workload (.omega.) will occur based on an historical 
distribution of workloads. The factor k is a proportionality constant. The 
probability of a given workload is assumed to be the combined probability 
that each of its parameters will occur. This is represented by equation 
(5). 
##EQU5## 
In a preferred embodiment, the workload parameters are assumed to be 
lognormally distributed so that the probability that a workload will occur 
historically is: 
##EQU6## 
where .mu..sub.i is the logarithmic mean, .sigma..sub.i is the standard 
deviation, and a.sub.i is minimum value for the workload parameter. Sample 
values for the logarithmic mean, standard deviation, and minimum value are 
shown in Table 5. 
TABLE 5 
__________________________________________________________________________ 
MIN MAX MEAN 
STANDARD 
WORKLOAD 
UNITS 
VALUE 
VALUE 
VALUE 
DEVIATION 
__________________________________________________________________________ 
1. 
Application 
0 time 0 1 0 
Idle fraction 
2. 
Application 
116 4096 byte 
0 infinite 
116 
Code RAM pg 
Demand 
3. 
Application 
193 4096 byte 
0 infinite 
193 
Data RAM pg 
Demand 
4. 
Application 
0.0999999 
megabytes 
0.1 infinite 
8.5 8 
RAM Demand 
999999999 
5. 
Local Paging 
1 fraction 
0 1 1 2 
Affinity 
6. 
Application 
1507.9198 
seconds 
0.000001 
infinite 
0.01 
2 
Sequential 
5929039 
Read 
Processing 
7. 
Application 
0.1991965 
seconds 
0.000001 
infinite 
0.01 
2 
Sequential 
53898435 
Write 
Processing 
8. 
Application 
302.30578 
seconds 
0.000001 
infinite 
0.01 
2 
Random Read 
8289707 
Processing 
9. 
Application 
0.00401599 
seconds 
0.000001 
infinite 
0.01 
2 
Random Write 
595049622 
Processing 
10. 
Application 
100000 seconds 
0.000001 
infinite 
100000 
Graphics 
Processing 
Application 
2481.7880 
bytes 
1 65536 
2048 
2048/3 
Sequential 
7408851 
Read Size 
Application 
2639.6738 
bytes 
1 65536 
2048 
2048/3 
Sequential 
3123312 
Write Size 
Application 
1946.3047 
bytes 
1 65536 
2048 
2048/3 
Random Read 
6425393 
Size 
Application 
5286.8933 
bytes 
1 65536 
2048 
2048/3 
Random Write 
4218392 
Size 
Application 
250 pixels 
1 1310720 
250 
Graphics Size 
Local 1 fraction 
0 1 1 
Sequential 
Read Affinity 
Local 1 fraction 
0 1 1 
Sequential 
Write Affinity 
Local Random 
1 fraction 
0 1 1 
Read Affinity 
Local Random 
1 fraction 
0 1 1 
Write Affinity 
20. 
Random Read 
2.1909522 
megabytes 
0.000001 
infinite 
1 2 
Extent 054493 
Random Write 
2.1909522 
megabytes 
0.000001 
infinite 
1 2 
Extent 0534625 
__________________________________________________________________________ 
The system uses a multivariate Gaussian error model as described in 
DeGroot, M., "Optimal Statistical Decisions," McGraw-Hill, New York, 1970. 
The following equation describes the probability: 
##EQU7## 
In a preferred embodiment, an equation solver such as "Solver" of 
Microsoft Excel is used to determine the workload that is the most 
probable. The inputs to the equation solver are (1) the model for 
calculating the predicted performance measurements, (2) the equations for 
calculating the probability of a workload, (3) an initial workload, (4) 
the actual performance measurements, and (5) the minimum, maximum mean and 
standard deviation values for each workload parameter. The solver 
determines the probability of the initial workload by using the model to 
generate the predicted performance measurements. The solver then 
calculates the probability of a workload. The solver then varies one of 
the workload parameters and then generates new predicted measurements and 
then the probability of the workload. Based on a comparison of the 
probability with the previous probability, the solver then again varies a 
workload parameter and the process is repeated. In one embodiment, only 
workload parameters corresponding to rows 4-9, 11-14, and 20-21 are 
varied. The other workload parameters are held constant. 
FIG. 14 is a flow diagram of the process for generates a recommendation to 
alleviate the bottleneck. The process selects various changes in hardware 
and software configuration and then applies the matching workload to the 
model with the selected configuration. The process then generates a report 
detailing performance and cost of each configuration. In step 1401, the 
process selects a new trial configuration. In step 1402, the process 
adapts the model to the selected trial configuration. In step 1403, the 
process applies the most probable workload to the model which has been 
modified to reflect the trial configuration. In step 1404, the models new 
estimates of computer system resource demand and device throughput are 
recorded. Resource demand is expressed in terms of device utilization, and 
throughput is expressed in terms of the frequency of accesses of 
particular types to the particular device. In step 1405, the price of the 
trial configuration is retrieved. In step 1406, the price and performance 
improvement are stored. In step 1407, if there are more configurations to 
check, then the process loops to step 1401 to the select the next 
configuration, else the process continues at step 1408. In step 1408, the 
process generates the price/performance report for the possible new 
configurations. 
Appendix A describes a further description of the techniques of the present 
invention. 
Although the present invention has been described in terms of preferred 
embodiments, it is not intended that the invention be limited to these 
embodiments. Modifications within the spirit of the invention will be 
apparent to those skilled in the art. The scope of the present invention 
is defined by the claims that follow.