Performance of I/O Subsystems | Advanced Computer Architecture | CS501_Lecture42

As-salamu alaykum. Welcome to the series of lectures on advanced computer architecture. We have been talking about the IO subsystems. We also discussed some of the peripherals. And we said that the most of the resources are loaded by the hard disks. The IO through the controllers, they just place a lot of resource constraint on the overall system. We would also like to look up and see the performance of the IO subsystems. When we compare the performance of CPU with the performance of IO subsystems, there would be some similarities and some other aspects would be different. You remember in the case of CPU performance, we have been talking about parameters like execution time. We also said about throughput or let us say in the form of mega instructions per second or megaflops. Now, we will have similar parameters for IO. However, there would be some aspects which are different. As an example, there is a parameter which we define as diversity. In the case of we say that what are the different IO devices to which a particular CPU or a computer system could be connected? Then, also we need to talk about the capacity. At simultaneously, how many different IO devices could be handled or connected? Think of hard disks. Can we connect 60 hard disks, 30 hard disks, or 10 hard disks simultaneously to a given processor? Now, if we think of similarities, then we will be talking about the IO bandwidth. In the case of IO bandwidth, this would define the throughput of the system. Just imagine we have hard disks. CPU sends a request and some data is to be transferred or read from the disk or an array of disks. Then, what is the maximum rate at which data could be transferred? That would be in the form of megabytes per second. Now, we could also talk of latency or the response time. Now, what is response time? We just say that we have initiated a request. When the request is initiated by CPU, for example, for reading a block from the hard disk, then in that case, we have initiated a task, and the task is, for example, reading a block of data through the IO port, you could say. Now, how much time would it take when we initiate that task or uh the request? This request might be placed in a queue because there might be some other disks already involved in exchange of IO or exchange of data. And then the end of that block when it has been totally transferred, that would be the total response time. So, that would mean the waiting time as well as the service time. So, you can imagine that IO device is just like a server. And it gets a call from CPU, for example. Then it has to serve. There would be some average time involved in that service and transferring of data. So, this would be the latency. Now, if we just say that hard disk, for example, is being utilized, we could say the total server utilization. We can talk and imagine in a very simple way, like a producer server model. Imagine we have a producer, which in this case would be CPU. The server would be the IO controller, whatever form it is. In between, we have a buffer. So, the calls would come into buffer. And then these calls would be served by the server. Now, throughput, for example, would mean that the server almost always remains busy. Right? When the calls come in and immediately one call is finished, one task is finished, then the second task is taken up by the server. The latency or the response time would depend on how many tasks are there in the queue and how fast is the server. Theoretically speaking, if in the queue there is no task ahead, then the latency would be low or the response time would be short. Now, if we think of a simple scenario and we say that we have a server utilization, that means the percentage of time for which the server remains busy. And second is the latency. Or third a parameter we can talk of throughput. Now, we can make a compromise and see how these parameters would be interconnected. Now, suppose you draw a plot and you think and on x-axis you plot the percentage utilization of the server from 0 to 100% and on x-axis you plot the latency, meaning the response time. Then you will see that initially for some part, as you increase the utilization, then there would be a linear increase in response time, the latency would increase. However, there would be a knee point and suddenly the response time would increase when we go beyond certain utilization, which may be for example around 80%. This is quite logical and you see that if we try to have more utilization from the server and keep the server busy all the time, then a long queue would be there and theoretically the system could explode and we could never achieve 100% utilization. So, there has to be a balance and this is what an architect would do to have a balance between the latency and throughput. So, throughput we'll see later on how do we control and how we can calculate the utilization of the system. This in turn would depend on the average number of calls that will get into the system and the average or mean time for service for that particular server. When we are talking about the performance of an IO subsystem, then there could be various tools that could be utilized. The first could be a straight away calculation as we did in the case of CPU performance in terms of like execution time. However, the IO systems are more complex and we have a queue or in the buffer, there there would be a waiting involved. Now, the second possibility could be to have a simulation. Like we could write write run the programs on the system having the IO subsystems as a part of the overall computer system and then calculate the performance in terms of throughput. Nevertheless, there is a very important uh tool that we could have and that is what we call the queuing theory. Based on this queuing queuing theory, we could use principles of statistics and make certain calculations and it would be a very simple and a handy tool. Now, when we look on a computer system, there could be different situations. Think of a telephone exchange. In a telephone exchange, the computer controls different activities of the different parts of the system. As an example, when the calls come in, these are just the telephone calls. And there would be an IU interface, and this would be controlled by a central processing unit. So, for example, we may not provide uh the 100% availability, and if there are 10,000 users in the exchange, we may provide, as an example, only 1,000 IU interfaces. That means simultaneously, there could be only 1,000 calls going through the system. Now, a simple design could be that we do not provide any buffer. We don't have any provision for queuing, then the system usually is called a loss system. And in the case of loss system, the provision is done in terms of how many switches do we need then to provide some redundancy, how many individual IU controllers do we need, then how many CPUs, for example, are there. This is a conventional design or what is called the dimensioning of the loss system. However, the present-day exchanges also provide you additional facilities. If you find some called party is busy, still you can have a provision of call waiting. You may have more than one call waiting for you. Once you finish one call, then you can attend the second call. This system is basically called a delay system, or it has actually a buffer or a delay line. This is similar to what we are talking about the IO subsystems. Now, let us consider a very simple model. We have a black box. This black box represents, as an example, an IO controller. At the input, we have arrival, arrival of different tasks. And as a task is done, then we have a departure. So, within this black box, we have the server. At the input, we have arrival, and at the output, we have departure of the finished tasks or finished calls. Now, if we expand and open up this black box, we could just consider the incoming calls into a buffer, and the output of the buffer is connected to a server. And this server, in this example, is only a single server. Now, this this example would consider a single-server model. Later on, we'll expand it and see multi-server model as well. Now, you can imagine that, in general, the system is dynamic. Different calls, different tasks are initiated, are being served, and uh then uh they leave the system. Now, how do we define the overall behavior of the system? There would be certain assumptions or certain inputs that we need to know about. The first thing that one should be clear is that we consider the steady-state behavior of the system. Actually, the system is dynamic. At any point of time, there would be a random number of tasks being originated, some of the tasks would be done and leave the system. Now, we are not interested in the instantaneous value of these calls. We are interested to know the average effect and see how many average number of calls are coming into the system, then how many average number of calls are being served by the server, and what is the average length or average number of calls in the buffer or in the queue. Now, we need to know some of the statistical parameters of the system. We make certain simple assumptions. In a simple computer system, we can imagine that the arrival is random. And secondly, the system doesn't have the memory. It means that the incoming calls, they are not correlated with each other. So, one call doesn't know how many previous calls are there into the system. So, therefore, the origination of calls is independent of each other. And we'll see in the next slide, we'll assume a Poisson's distribution. We will also assume the exponential time between two consecutive calls. That means the distribution of the time is exponential. Similarly, the service time by the server is also assumed to be exponential. Now, we will calculate the average effect and look into a very simple formula. This is called Little's Law, and that says that the mean time required for the server is equal to the average rate of arrival into the mean time for the server. Although this formula appears to be very simple, but it is very handy and it is pretty useful in simple calculations for system utilization and other parameters which we are going to look into the next slide. As we said, we have a very simple model. We have a queue or a waiting line at the input. The tasks are arriving with an arrival rate. At the output of the queue, we have an IO controller and the device together, we call it a server. Through an observation time, which we call T observation or T system. We say that on the average a given number of calls are coming into the system. We can call it N task and the observation time could be divided into a time spent in the queue and a time spent in the server. Through a simple algebra, you can come to the result which we call Little's Law. We'll not go into the simple derivation, but you will see and you can write the mean number of tasks in the system could be written as equal to arrival rate into the mean response time. Now, this is really a very powerful relationship. We just look into simple definitions of certain other parameters and then through other examples, we will utilize this formula to illustrate the performance. Now the time TS is the server time. It corresponds to the average time to service a task. Now the average service rate would be reciprocal of this time which is traditionally represented as mu for the books in statistics. TQ is the average time per task for remaining in the queue. TS is the average time per task in the system. This is actually defined as the response time. And this would be mathematically equal to the sum of the queue time and the server time. So you could write TS or T response equal to TQ plus TS. The arrival rate is the average number of arriving tasks per second and we could represent it as lambda. LS is the average number of tasks in the service. That means the length of server, average length of the queue, that is the number of tasks waiting to be served in the queue. LS is the average number of tasks in the system which is the sum LQ plus LS. In this simple example, we have only one task in the server. It's a single server. And then we will have LQ plus one is equal to LS. So the total number of calls in the system would be one in the server and remaining in the queue. Now the parameter which we are interested in is the system time or the response time, which we have said is sum of the queue and the server time. The mean number of tasks in the server is simply given by arrival rate into the time for the server. And we can write a simple relationship which is another form of Little's law. Server utilization would be equal to the arrival rate into the time for the server. The unit of time should be same in both cases. You can just call this server utilization would be dimensionless and its value would be between zero and one. It cannot exceed one, otherwise the system would explode. You can also call it as traffic density. Consider a very simple example. We have an IO system with a single disk and this disk has an arrival rate of 100 tasks per second. The service time is 5 milliseconds per call or per task. Calculate the system utilization. So, the server utilization could be written, as we said, as arrival rate into TS, the service time, which in this case is 100 multiplied by 0.005, which is 0.5. So, the server utilization is 50%. So, on the average, 50% of the time the server is busy and 50% it is idle. Through this example, we have seen that the server utilization will depend on two parameters. First, on the arrival rate. Larger the number of task on the on the average coming into the system, more would be the utilization. Secondly, what is the average time required for each task to be served? So, if a server is faster, then its utilization would be smaller. And if it takes too long to serve a call, then it its throughput would be small. So, indirectly, you could say that the utilization would depend on the IO bandwidth and the rate of arrival into the system. Now, the rate of arrival could be different and it would have a statistical distribution. Now, we could use different distributions, but one of the very popular and common distribution would be Poisson's distribution. Now, for a given time of observation, which we we could call T observation, and for a given rate of arrival, which we call lambda, we could write the Poisson's distribution as shown in the next slide. The Poisson's distribution could be written mathematically as P K. P K represents the probability of K tasks in the system or arrival of K tasks is equal to E raised to power minus A into A raised to power K divided by K factorial. And what is A? A is just the product of the arrival rate into the time that we are observing or the time elapsed. So, if lambda, for example, is the arrival rate, capital T is the time for which we are observing or the time in which we are interested. A would be lambda times T. Now, it is important to realize that out of this distribution, we could calculate the mean value and also the variance. It's easy to show that Poisson's distribution has a mean value and variance which is equal. In a normalized fashion, if we write the parameter C squared as the ratio of variance to the square of arithmetic mean or C would be just under root of that, indicating the ratio of standard deviation to the arithmetic mean, then particularly for Poisson's distribution, we would have value of C equal to 1. Now, in fact, we could have different distributions. One extreme could be where the service time is fixed. That's an example of a constant service time. And that would mean the value of C in that case would be zero because for a fixed mean value, the standard deviation is zero for all service calls, for all all tasks, the time service time is the same. On the other hand, as we have just said that for Poisson's distribution, the value of C is just one, that is the standard deviation is equal to the mean value. Now, we are interested in calculating the total time or total response time. And as we said that this response time has got two components. One is the time in the queue for just waiting. And then, the time which is required for the service. That is, the total time would be Q time plus the time in the service. And the time in the service, on the average, we can say this mean value would depend on which particular distribution we take. And it can be indicated by a very simple formula as shown in the next slide. Now, the total time, as we said, is just the length in the queue into the time for service for each task plus the mean time that is required for the task in the server, right? That is, on the average. So, based on this, we could say that the time required for the task, which is with the server, could be written as average residual service time is equal to half into weighted mean time into 1 + C squared within brackets. So, as an example, if C was zero then average time would be just half. That is, the remaining time required for servicing would be half the average time. On the other hand, for Poisson's distribution, if we put the value of C equal to zero the average residual service time would be just equal to half into weighted mean time into two. So, it would be equal to the mean waiting time. Let us consider a very simple example for calculating the time in the queue with some figures in the next example. Now, let us consider all tasks in the queue and that is the L queue is the length of the queue ahead of the new task that must be completed before the task can be serviced. Each takes on the average TS, which is the server time. If the task is at the server, it takes average residual service time to complete. The chance the server is busy is the server utilization. So, server utilization, as we said, has a value between 0 and 1. And it would correspond to the probability that server is busy. This leads to a very simple formula. TQ is equal to LQ into TS plus server utilization into average residual service time. If we just replace simple figures and I write TQ is equal to eta, which corresponds to server utilization, into TS, the time for service, plus lambda times TQ. Lambda is the arrival rate. TQ is the time required in the queue. And TS is the time for service. Interchanging the value of TS and TQ, we just simply see that TQ is equal to TS into eta divided by 1 minus eta. This is a very simple relationship and very useful. For the last example, we saw that service utilization was 0.5. So, if we put in this formula, then we see TQ is equal to 0.5 divided by 1 minus 0.5 into the service time, which is just given as an example 5 milliseconds. So, therefore, the queue time would be 5 milliseconds. Now, as we said that we have made certain assumptions, and the assumptions are as follows. First of all, we assume that arrival is random. That is the distribution of the incoming tasks is Poisson's, or it has Poisson's distribution. The system is assumed to be in steady state or in equilibrium, and that would mean that on the average the number of tasks coming into the system is equal to the number of tasks going out of the system. For For this particular example, we have assumed a single server. So, technically, you could say that we have a Markov arrival or the Markov distribution of the service pattern. So, this we could write as M/M/1. One would mean a single server, the Markov chain at the input and a Markov chain at the output. Now, we also assume that the queue length is infinite. That means there is no limitation. We are not thinking of a truncated buffer. So, theoretically, the buffer could vary anywhere between zero and infinity. We have also assumed that the service The service to the next call is taken immediately after finishing the first call. That means the server doesn't need any waiting time in between. If it is, we can accommodate that later on. Right? With these assumptions, it's a very simple relationship to evaluate the system utilization or throughput and all other parameters which we have defined previously could be calculated. A processor can handle 20 disk IOs per second. The average time to service one call is 10 ms. Calculate the parameters. Number one, average disk utilization. Number two, average time in the queue. And number three, the average response time. For the first one, the average disk time to serve a task is equal to 10 ms in this example. So, the disk utilization would be arrival rate into the service time. And remember the unit of time in both cases should be the same. We have average number of tasks per second as 20. The average disk time to serve a task is 10 ms, that is 0.01 second. So, the utilization or the disk utilization would be lambda times TS, that is 20 into 0.01, which is 0.2. That is 20% is the utilization of the disk. Second part says calculate the average time in the queue. So, TQ, as we calculated earlier, could be written as TS into the system utilization divided by 1 minus the system utilization, which in this case would be 10 into 0.2 divided by 0.8, which turns out to be 2.5 milliseconds. So, any task on the average would have a waiting time in the queue of 2.5 milliseconds. Now, in part three, we are supposed to calculate the average response time or the overall system's time. And this would be sum of the time spent in queue plus the time on the average spent in the server. And as we said, for this case, we have the value of C is equal to 1 with Poisson's distribution, the average remaining time would be 10 milliseconds. The queue time is 2.5 milliseconds. So, 10 + 2.5 is 12.5 milliseconds, which corresponds to the response time. It's interesting to note that the two components of the response time correspond to one for the service, one for the queue. In this case, the queue time is 2.5 milliseconds, since the system utilization or disk utilization is low. So, therefore, on the average, the task has to wait for a lesser time. If we increase the system utilization, or in this case, the disk utilization, we increase it, the waiting time would increase correspondingly, and the total response time would increase. Now, for these examples, we have discussed only a single server. If we want to increase the throughput, we could have more than one server. And we could have a model as an example, M/M/2, which would mean two servers. Let us consider what would be the change in the corresponding formula in the next slide. Now, if we have n number of servers, then the formula corresponding to n servers would be modified and through simple mathematics, we could calculate the utilization would be equal to arrival rate into TS divided by NS, where NS is the number of servers, right? The utilization would be decreased. As an example, if our single server the utilization was 0.8 and we increase the number of servers to two, the utilization would be 0.4, 40%. So, on the average, we assume both the servers are identical and half of the work would be done by each. Length of the queue, LQ, would be equal to arrival rate into TQ. The time for waiting in the queue would be TQ is equal to TS multiplied with the probability of tasks being greater than the number of servers, NS. That is, when this is the situation, the system would be congested and waiting would be required. The task would be placed in the queue divided by NS into 1 minus the utilization. So, for this case, we have an MM1 model. That is, NS would correspond to the number of servers. So, the probability of tasks greater than NS could be calculated as NS into utilization, which we call eta, raised to power NS divided by NS factorial into within brackets 1 minus eta and this whole is multiplied with the probability of having zero tasks in the queue. That means no queue at all. Suppose we increase the number of disks to two. The average arrival rate is 20. And the service time for each of the two disks is 40 milliseconds. Now, let us calculate the server utilization, which is equal to arrival rate into TS, the service time, divided by NS, the number of servers. So, putting down the values, 20 is the arrival rate into 0.04 is the service time divided by two, which is equal to 0. 4. So, if there was only one disk, the utilization would have been 0.8 and it has been halved, it decreases to 0.4. Now, then we calculate the probability of no tasks in the queue, which is P0. Putting down the figures, you just see it turns out to be 1 over 2.333. Now, we use this result to calculate the probability of tasks in the queue, which is just put the value of utilization and probability of zero tasks, it turns out to be 0. 2 2 9. And finally, the waiting time in the queue, just TQ, is equal to TS into the probability of tasks being greater than NS divided by NS into within brackets 1 minus the utilization, which turns out to be .00 38. So, you see that in this case the average response time would be the response time 40 milliseconds plus the waiting time which is just 3.8 milliseconds. It would become 43. 8 milliseconds which is a significant improvement by adding up an additional server. Through these examples, we have seen how to evaluate the performance of IO systems through the utilization of queuing theory. However, for more complex systems, we can't do that. Consider the online transaction processing. In that case, like airline booking, a number of customers are coming up. You have an arrival rate and you have to dispose of the calls or serve the customers. This would be a typical example of transaction processing. Similarly, it could be online. Then it would be called online transaction processing. And therefore, to evaluate the IO performance in such cases, we have benchmark programs. And these benchmark programs could be similar to what we have seen for the CPU. Nevertheless, we uh need to incorporate the program in such a way that the IO calls reflect the real situation. There are two important programs which could be used as benchmark programs. One could be the spec. And for the spec, similar program what but with online transaction processing are available or we could we could have the online trans- transaction processing by program which would we could call TPC-C that represents the version for TPC-C program. And the after running these bench- benchmark programs on a real system, the results could be compared. Some of these results are just indicated in the next slide for some typical results after running on some typical systems. TPCT is a typical benchmark program given by the transaction processing council. Now, different versions could be used for different applications. C, for example, is a typical complex query for online transaction processing. It could have typically a data size of 100 to 3,000 GB, and its performance metric could be in the new order transactions per minute. And it was developed in 1992 September. TPCC gives the measurement given by TPCC is in the form of transactions per minute given as TPM-C. And the price of the system including hardware, software, and the maintenance support is also given by the benchmark program. The TPC benchmarks were the first and in some cases are still the only ones used and available for online transaction processing. We have another important benchmark and that is from SPEC. And we call it the system level file server. This is This is SFS. The SPEC benchmark effort is best known for its characterization of the processor performance. However, it has also created a benchmark in the other fields in 1990, particularly for the online uh transaction processing and this is generally called SFS. It evaluates the system and gives, again, in terms of the protocols and different versions used. As we have noticed in earlier lectures that a lot of time in reading data from the disk is involved in mechanical delays. In order to avoid these mechanical delays, the operating system has to play a very important role. And the synchronization of the data read from the disk is done by the operating system. So, a number of disks are connected to a given controller and the operating system give provides the environment at supervisory level to coordinate the data read from different disks. This concept of asynchronous IO and the behavior of the operating system is indicated in the next slide. The natural path to higher IO performance is parallelism, which gives many disks to be connected simultaneously and a simultaneous access of data is provided through the operating system. This is indicated in the slide. The straightforward approach to IO is to request data and then start using it. The operating system then switches to another process until the desired data is available. And then the operating system switches back to the request which was in process. Such a style is called synchronous IO. The process waits until the data has been there and it has been read from the disk. The alternative model is for the process to continue after making a request and not to wait for the data to arrive. And then it is blocked until it tries to read the requested data. Such asynchronous IO allows the process to continue and making requests so that many IO requests can be operated simultaneously. Asynchronous IO shares the same philosophy fee as we have discussed in caches and in out of order CPU, which gives a larger throughput in the form of bandwidth. So, we will have a larger IO bandwidth available for this scenario. We have seen that for an IO subsystem, the performance is dictated by two important parameters, the latency and the bandwidth. For a given IO bus, the bandwidth would depend on effectively how quickly we can pass on data through that particular bus. Now, for the better throughput or to increase the effective IO bandwidth, we have to change the architectural strategy. And this strategy we have mentioned earlier in one of the lectures with reference to the CPUs, where we used multiple CPUs. Similarly, if we have multiple IO devices and instead of sharing just one IO bus, we could use a switch. If we have an n by n switch, then any one of the n devices from input could be connected to the other side, which could be CPU. So, the controller IO controller could have instead of a single bus, a switch. And this would effectively increase the bandwidth of the IO and a much larger amount of data could be transferred from the database onto the system. Now, this is extremely important in a real-time system, where we are having online transaction processing. Large databases are available and it would not be available in the form of one computer. We can access different computers on the web. And through this web, we could have effectively a larger throughput. So, suppose we have a connection of computers over LAN within a building for an airline booking system. So, a number of servers would be available, a number of IO devices would be available, and these would be connected together through a switch instead of a bus. Today, we have discussed the performance of the IO subsystems. We have seen that as far as the performance of IO subsystems is concerned, some of the parameters are similar to that for the performance of CPUs. There are other parameters which are different. Now, one of the tools which was not available, or we did not use it with reference to the CPUs, was the queuing aspects or the queuing theory. We have discussed today some of the fundamental features of queuing theory, and we have seen how to calculate the utilization of the system and the IO performance if we are given a particular system. So, for a single server, it is relatively easy, and as the number of servers increase, application of queuing theory gradually becomes more and more more complex. Eventually, we said that in a real-time situation, it might be very difficult to calculate the performance through queuing theory. In such a situation, we need to apply simulations. And for these simulations, we need to run certain benchmark programs. We have seen two important benchmark programs given by two different organizations. Running these programs would give us the performance of IO in the form of IO bandwidth available or the throughput, and secondly, the average response time or the latency into the system. And this is a very important feature of the IO to evaluate for an architect how it is performing. In general, we have seen that as the utilization of the server increases, the response time would also increase. That means on the average, the idle time for the server would be low and correspondingly the waiting time would increase and queue would gradually grow. The architect has to really strike a balance between latency and the IO bandwidth. And therefore, ensure really a good performance for for from the IO subsystem. Now today, we stop at this point with the ideas regarding performance of the IO subsystems. That's it for today. Till next time. Allah Hafiz.