Browsing by Author "Golubchik, Leana"
Now showing 1 - 11 of 11
Results Per Page
Sort Options
Item Automated Techniques for Designing Embedded Signal Processors on Distributed Platforms(1998-11-04) Kang, Dong-In; Gerber, Richard; Golubchik, LeanaIn this paper, we present a performance-based technique to help synthesize high-bandwidth radar processors on commodity platforms. This problem is innately complex, for a number of reasons. Contemporary radars are very compute-intensive: they have high pulse rates, and they sample a large amount of range readings at each pulse. Indeed, modern radar processors can require CPU loads of in high-gigaflop to tera-flop ranges, performance which is only achieved by exploiting the radar's inherent data parallelism. Next-generation radars are slated to operate on scalable clusters of commodity systems. Throughput is only one problem. Since radars are usually embedded within larger real-time applications, they also must adhere to latency (or deadline) constraints. Building an embedded radar processor on a network of workstations (or a NOW) involves partitioning load in a balanced fashion, accounting for stochastic effects injected on all software-based systems, synthesizing runtime parameters for the on-line schedulers and drivers, and meeting the latency and throughput constraints. In this paper, we show how performance analysis can be used as an effective tool in the design loop; specifically, our method uses analytic approximation techniques to help synthesize efficient designs for radar processing systems. In our method, the signal-processor's topology is represented via a simple flow-graph abstraction, and the per-unit load requirements are modeled stochastically, to account for second-order effects like cache memory behavior, DMA interference, pipeline stalls, etc. Our design algorithm accepts the following inputs: (a)~the system topology, including the thread-to-CPU mapping, where multi-threading is assumed to be used; (b) the per-task load models; and (c) the required pulse rate and latency constraints. As output, it produces the proportion of load to allocate to each task, set at manageable time resolutions for the local schedulers; an optimal service interval over which all load proportions should be guaranteed; an optimal sampling frequency; and some reconfiguration schemes to accommodate single-node failures. Internally, the design algorithms use analytic approximations to quickly estimate output rates and propagation delays for candidate solutions. When the system is synthesized, its results are checked via a simulation model, which removes many of the analytic approximations. We show how our system synthesizes a real-time synthetic aperture radar, under a variety of loading conditions. Also cross-referenced as UMIACS TR # 98-57Item Bolshoi - A Modeling Spreadsheet (Improving Usability of Complex Analytical Modeling Tools)(2000-03-07) Cheng, William C.; Golubchik, LeanaSpreadsheet programs are very popular financial modeling tools because they allow users to juggle numbers and formulas with a powerful yet intuitive and easy to understand user interface; also, they often are equipped with sophisticated numerical analysis packages for data analysis and powerful presentation utilities for visualizing results. Computer systems performance and reliability modeling tools of today, on the other hand, have un-intuitive user interfaces and are difficult to learn and use. In this work, we propose to design, build, and evaluate Bolshoi, a modeling spreadsheet, with the goal of putting modeling tools comfortably in the hands of non-expert users. In this proposal, we address management of complexity that exists in performance and reliability analysis of real computer and communication systems. Specifically, we propose to do so through the design and development of an advanced modeling tool. Our tool will provide two important functions: (1) a proper interface for building models that will allow system designers not just to define their models, but visualize them in various ways and (2) easy plug-in of existing and future advanced solution techniques. We call this tool Bolshoi, a Modeling Spreadsheet, because it has a spreadsheet-type interface as detailed below. Performance evaluation of real systems is complex, suffers from scalability problems (or the so-called ``state explosion'' problem) and in many cases requires advanced computational techniques. Often, advanced computational techniques are based on exploitation of ``special structure'' in the models (the primary way to deal with state explosion besides getting a bigger machine). With large and complex models, these special structures are very expensive to expose automatically as it involves searching through a combinatorial number of permutations. Proper visualization of models can greatly assist in the discovery of these special structures so that state space reduction techniques can be applied. Discovery of special structure regularly contributes to many orders of magnitude in computational efficiency. Furthermore, models are often defined over infinite state spaces. We believe that a spreadsheet paradigm is ideal for visualizing such models. Without proper modeling tools, much effort and money is wasted by the computer industry, and moreover, the probability of a successful outcome is low. Thus, a good tool is crucial to advances in the state of the art in performance modeling as well as to successful design of systems in the industry. Every system designer should be able to integrate the use of a performance modeling tool into his/her design process. He/she should be able to easily ask ``what-if'' type questions, explore possible design choices, and make decisions based on quantitative results rather than ``gut feeling''. We believe that a modeling spreadsheet is the right abstraction for such tasks, and furthermore, to the best of our knowledge this abstraction has not been exploited for performance evaluation tool purposes. We believe that the approach proposed here will have a significant impact on future performance tool designs as well as make significant strides in wide-spread use of performance evaluation techniques among computer and communication system designers. Furthermore, a modeling tool that does not require expert-level methodology knowledge is also an excellent undergraduate-level and graduate-level educational tool. Opportunities for hands-on experience with modeling and performance evaluation as well as the ability to add new techniques to the tool greatly improve the educational experience of students and their future ability to apply what they have learned in class to design of real computer and communication systems. (Also cross-referenced as UMIACS-TR-2000-10)Item Data Migration on Parallel Disks(2003-12-18) Golubchik, Leana; Khuller, Samir; Kim, Yoo-Ah; Shargorodskaya, Svetlana; Wan, Yung-Chun (Justin)Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high demand storage servers are used as web servers or multimedia servers, for handling high demand for data. As the system is running, it needs to dynamically respond to changes in demand for different data items. There are known algorithms for mapping demand to a layout. When the demand changes, a new layout is computed. In this work we study the data migration problem, which arises when we need to quickly change one layout to another. This problem has been studied earlier when for each disk the new layout has been prescribed. However, lack of such information leads to an interesting problem that we call the correspondence problem, whose solution has a significant impact on the solution for the data migration problem. We examine algorithms for the data migration problem in more detail and identify variations of the basic algorithm that seem to improve performance in practice, even though some of the variations have poor worst case behavior. UMIACS-TR-2003-115Item Design of Scalable Continuous Media Servers with Dynamic Replication(2001-05-10) Chou, ChengFu; Golubchik, Leana; Lui, John C.S.; Chung, I-HsinMultimedia applications place high demands for quality-of-service (QoS), performance, and reliability on systems. These stringent requirements make design of cost-effective and scalable systems difficult. Therefore efficient adaptive and dynamic resource management techniques in conjunction with data placement techniques can be of great help in improving performance, scalability and reliability of such systems. In this paper, we first focus on data placement. In the recent past, a great deal of work has focused on "wide" data striping as a way of dealing with load imbalance problems caused by skews in data access patterns. Another approach to dealing with load imbalance problems is replication. The appropriate compromise between the degree of striping and the degree of replication is key to the design of scalable continuous media (CM) servers. In this work we focus on evaluation of this compromise in the context of a hybrid CM server design. Changes in data access patterns lead to other questions: (1) when should the system alter the number of copies of a CM object, and (2) how to accomplish this change. We address (1) through an adaptive threshold-based approach, and we use dynamic replication policies in conjunction with a mathematical model of user behavior to address (2). We do this without any knowledge of data access patterns and with provisions for full use of VCR functionality. Through a performance study, we show that not only does the use of this mathematical model in conjunction with dynamic resource management policies improves the system's performance but that it also facilitates reduced sensitivity to changes in:(a) workload characteristics, (b) skewness of data access patterns, and (c) frequency of changes in data access patterns. We believe that not only is this a desirable property for a CM server, in general, but that furthermore, it suggests the usefulness of these techniques across a wide range of continuous media applications. (Cross-referenced as UMIACS-TR-2001-21)Item Evaluation of Tradeoffs in Resource Management Techniques for Multimedia Storage Servers(1998-11-18) Golubchik, Leana; Liu, John C. S.; Souza, Edmundo de Silva e; Gail, H. RichardMany modern applications can benefit from sharing of resources such as network bandwidth, disk bandwidth, and so on. In addition, many information systems store (or would like to store) data that can be of use to many different classes of applications, e.g., digital libraries type systems. Part of the difficulty in efficient resource management of such systems can then occur when these applications have vastly different performance and quality-of-service (QoS) requirements as well as resource demand characteristics. In this work we present a performance study of a multimedia storage system which serves multiple types of workloads, specifically a mixture of real-time and non-real-time workloads, by allowing sharing of resources among these different workloads while satisfying their performance requirements and QoS constraints. The broad aim of this work is to examine the issues and tradeoffs associated with mixing multiple workloads on the same server to explore the possibility of maintaining reasonable performance and QoS requirements without having to partition the resources. The main contribution of this work is the exposition of the tradeoffs involved in resource management in such systems. Although many different resources can be considered, here we concentrate mostly on the I/O bandwidth resource. The performance metrics of interest are the mean and variance of the response time for the non-real-time applications and the probability of missing a deadline for the real-time applications. The increased use of buffer space resources is also considered as a tradeoff for improvements in the above stated performance metrics, i.e., response time and probability of missing deadlines. (Also cross-referenced as UMIACS-TR-98-30)Item On a Graph-theoretic Approach to Scheduling Large-scale Data Transfers(2002-04-04) Cheng, William C.; Chou, Cheng-Fu; Golubchik, Leana; Khuller, Samir; Wan, Yungchun (Justin)In this paper we consider the problem of moving a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion conditions, the choice of paths by the network may be poor. By choosing an indirect route at the application level, we may be able to obtain substantially higher performance in moving data through the network. We formulate this data transfer (collection) problem as a network flow problem. We show that by using a min-cost flow algorithm on an appropriately defined time-expanded (network) graph, we can obtain a data transfer schedule. We show that such schedules can be an order of magnitude better than schedules obtained by transferring data directly from each host to the destination. In fact, this holds, even though we make no assumptions about knowledge of the topology of the network or the capacity available on individual links of the network. We simply use end-to-end type information and compute a schedule for transferring the data. Finally, we also study the shortcomings of this approach in terms of the gap between the network flow formulation and data transfers in a wide-area network. Also UMIACS-TR-2002-04Item Performance of Batch-based Digital Signatures(2002-04-04) Cheng, William C.; Chou, Cheng-Fu; Golubchik, LeanaA Digital Signature is an important type of authentication in a public-key (or asymmetric) cryptographic system, and it is in wide use. The performance of an Internet server computing digital signatures online is limited by the high cost of modular arithmetic. One simple way to improve the performance of the server is to reduce the number of computed digital signatures by combining a set of documents into a batch in a smart way and signing each batch only once. This reduces the demand on the CPU but requires extra information to be sent to clients. In this paper, we investigate performance of online digital signature batching schemes and show that significant computational benefits can be obtained from batching without significant increases in the amount of additional information that needs to be sent to the clients. We also give a semi-Markov model of a batch-based digital signature server and its approximate solution. We validate the solutions of the analytical model through both emulation and simulation. Also UMIACS-TR-2002-03Item A Performance Study of a Large-scale Data Collection Problem(2002-08-01) Chou, Cheng-Fu; Wan, Yung-Chun (Justin); Cheng, William C.; Golubchik, Leana; Khuller, SamirIn this paper, we consider the problem of moving a large amount of data from several source hosts to a destination host over a wide-area network, i.e., a large-scale data collection problem. This problem is important since improvements in data collection times in many applications such as wide-area upload applications, high-performance computing applications and data mining applications are crucial to performance of those applications. Existing approaches to the large-scale research are transferring data either directly, i.e., direct methods, or using ``best''-path type of application-level re-routing techniques, which we refer as non-coordinated methods. However, we believe that in the case of large-scale data collection applications, it is important to *coordinate* data transfers from multiple sources. More specifically, our coordinated method would take into consideration the transfer demands of all source hosts and then schedule all data transfers in parallel by using all possible existing paths between the source hosts and the destination host. We present a performance and robustness study of different data collection methods. Our results showed that coordinated methods can perform significantly better than non-coordinated and direct methods under various degrees and types of network congestion. Moreover, we also showed that coordinated methods are more robust than non-coordinated methods under inaccuracies in network condition information. Therefore, we believe that coordinated methods are a promising approach to large-scale data collection problems. Also UMIACS-TR-2002-62Item A Performance Study of Dynamic Replication Techniques in Continuous Media Servers(1998-11-03) Chou, ChengFu; Golubchik, Leana; Lui, John C.S.Multimedia applications are emerging in education, information dissemination, entertainment, as well as many other applications. The stringent requirements of such applications make design of cost-effective and scalable systems difficult, and therefore efficient adaptive and dynamic resource management techniques can be of great help in improving resource utilization and consequently improving performance and scalability of such systems. In this paper, we focus on threshold-based policies, for dynamic resource management, and specifically, in the context of continuous media (CM) servers. Furthermore, we propose a mathematical model of user behavior and show, through a performance study, that not only does the use of this model in conjunction with dynamic resource management policies improves the system's performance but that it also facilitates significantly reduced sensitivity to changes in: (a) system architecture, (b) workload characteristics, (c) skewness of data access patterns, (d) frequency of changes in data access patterns, and (e) choice of threshold values. We believe that not only is this a desirable property for a CM server, in general, but that furthermore, it suggests the usefulness of these techniques across a wide range of continuous media applications. Also cross-referenced as UMIACS-TR-98-61Item Striping Doesn't Scale: How to Achieve Scalability for Continuous Media Servers with Replication(1999-09-02) Chou, ChengFu; Golubchik, Leana; Lui, John C.S.Multimedia applications place high demands for QoS, performance, and reliability on storage servers and communication networks. These, often stringent, requirements make design of cost-effective and scalable continuous media (CM) servers difficult. In particular, the choice of data placement techniques can have a significant effect on the scalability of the CM server and its ability to utilize resources efficiently. In the recent past, a great deal of work has focused on ``wide'' data striping as a technique which ``implicitly'' solves load balancing problems; although, it does suffer from multiple shortcomings. Another approach to dealing with load imbalance problems is replication. The main focus of this paper is a study of scalability characteristics of CM servers as a function of tradeoffs between striping and replication. More specifically, striping is a good approach to load balancing while replication is a good approach to ``isolating'' nodes from being dependent on other system resources. The appropriate compromise between the degree of striping and the degree of replication is key to the design of a scalable CM server. This is the topic of our work. Also cross-referenced as UMIACS-TR-99-45Item ViPEr-HiSS: A Case for Storage Design Tools(1999-10-27) Golubchik, Leana; Dunnick, Joseph; Hollingsworth, Jeffrey K.The viability of large-scale multimedia applications, depends on the performance of storage systems. Providing cost-effective access to vast amounts of video, image, audio, and text data, requires (a) proper configuration of storage hierarchies as well as (b) efficient resource management techniques at all levels of the storage hierarchy. The resulting complexities of the hardware/software co-design in turn contribute to difficulties in making accurate predictions about performance, scalability, and cost-effectiveness of a storage system. Moreover, poor decisions at design time can be costly and problematic to correct in later stages of development. Hence, measurement of systems after they have been developed is not a desirable approach to predicting their performance. What is needed is the ability to evaluate the system's design while there are still opportunities to make corrections to fundamental design flaws. In this paper we describe the framework of ViPEr-HiSS, a tool which facilitates design, development, and subsequent performance evaluation of designs of multimedia storage hierarchies by providing mechanisms for relatively easy experimentation with (a) system configurations as well as (b) application- and media-aware resource management techniques. (Also cross-referenced as UMIACS-TR-99-69)