Department: Computer Science and Engineering ![[clear]](close-x.png "Remove this limiter")
238 matches in the database.
These are records: 1 - 30.
[1] [2] [3] [4] [5] [6] [7] [8]
1.
Adcock, Bruce M.
Working Towards the Verified Software Process.
Degree: PhD, Computer Science and Engineering, 2010, Ohio State University
► Numerous pieces of the software verification puzzle need to fit together in…
(more)
▼ Numerous pieces of the software verification puzzle need to fit together in order to achieve that vision. First, there must be a programming language that gives some hope of specifying and implementing verifiable code ("assertive code"). Second, there needs to be a correct procedure for generating verification conditions (VCs) from this assertive code. Third, there must be one or more automated theorem provers to process the VCs and determine their validity or invalidity. Finally, it is essential that there is an interface for programmers to write their code and verify or debug it without forcing them to understand how particular automated theorem provers work. This dissertation covers the latter two of these topics using the Resolve language and verification framework. A common failing of most automated verification techniques is the inability to be truly automatic in all circumstances. Experience with proof assistants shows that they need to be "nudged" in the correct direction by an intervening human, in all but the simplest cases. Otherwise, the option is to use tools not geared to handle the rich mathematics used in the Resolve programming language. By using specialized decision procedures that take into account the known structure of the generated VCs, we strive to accomplish one of two possibilities for each VC: first, we hope to prove it outright; otherwise, we hope to simplify the VC to such an extent that another prover is able to handle it. We detail work on SplitDecision, a tool that simplifies VCs for Resolve. We further explain work that has helped to ensure SplitDecision is among the fastest and least memory intensive automated provers available, by introducing "lazy copying" to Resolve/C++ (in which SplitDecision is written), with specific work to maintain the value semantics integral to Resolve's design. Sometimes (perhaps this is even the modal case) at least one VC is not proved because it is not valid. It is clear that the ways we present errors and debug code must be rethought in a verified software paradigm. This area of research has received little attention to date, so we lay out criteria for how to approach debugging, along with potential methods of doing so.
Advisors/Committee Members: Weide, Bruce.
Subjects: Computer Science
Keywords: Software engineering; software verification; automated theorem prover; lazy copying; Resolve; debugging
More Like This
2.
Agarwal, Abhijat.
A New Approach to Spatio-Temporal Kriging and Its Applications.
Degree: MS, Computer Science and Engineering, 2011, Ohio State University
► Stochastic spatio-temporal variability is often observed in naturally occurring phenomena. It had…
(more)
▼ Stochastic spatio-temporal variability is often observed in naturally occurring phenomena. It had always been a challenge to predict their behavior in space and time. Statistical techniques exist that may be united to model and predict the spatio-temporal behavior of these phenomena. In this research we present a new approach to spatio-temporal data analysis. A new Spatio-Temporal Kriging model was built to predict the spatio-temporal behavior of atmospheric temperature data, gathered from heterogeneous sensors for over 10 years at 63 locations in the US. Kriging interpolates the best linear unbiased estimate of a value at an unobserved point in space, based on the weighted linear combination of surrounding observations, minimizing the prediction error. Spatial and temporal associations in the data were initially modeled separately, using Universal Kriging (UK) and Autoregressive (AR) techniques respectively and then combined to spatio-temporally predict temperatures, k days into the future in a given spatial domain. ARIMA (Autoregressive Integrated Moving Average) model was used to compare the performance of our Spatio-Temporal Kriging model. Our model performed twice as better with 2.47°C of average standard error (SE) in prediction estimates as compared to 4.49°C from ARIMA. Confidence interval (95% CI) for prediction estimates from ARIMA model was ±8.80°C as compared to ±4.84°C from our Spatio-Temporal Kriging model. Uncertainty in predictions observed from both the models may be largely associated to the presence of strong temporal correlation in the observations at locations near the Great lakes, also observed from slowly decaying autocorrelation function (ACF) at these locations. A new Space-Time linear model was also built using regression that yielded poor results, because it only captured the effect of latitude on temperature, i.e. temperature drops as we move up north. We also introduced a novel concept of Kriging based virtual sensor (KVSense) that may be used for temporarily replacing the faulty wireless sensor(s) and also to emulate the working of a real sensor at inaccessible areas. We concluded by discussing, possible novel energy harvesting (energy conservation and wireless sensor power rejuvenation) strategies for wireless sensor networks (WSN) configured in a spatial domain based on mined spatio-temporal knowledge on availability of ambient (sunlight, wind, etc.)
Advisors/Committee Members: Parthasarathy, Srinivasan.
Subjects: Climate Change; Computer Science; Geography; Statistics
Keywords: Spatio-Temporal; Universal Kriging; ARIMA; Prediction
More Like This
3.
Agrawal, Artika.
Intelligent Techniques for Data- Information- Knowledge Evolution.
Degree: MS, Computer Science and Engineering, 2011, Ohio State University
► The quality of data in an Enterprise Data Warehouse (EDW) plays a…
(more)
▼ The quality of data in an Enterprise Data Warehouse (EDW) plays a very important role in decision making activities like cross selling products and services or to identify unmet market needs etc. Every organization puts in a lot of resources to maintain data of high quality, in order to make informed decisions regarding market trends or to create business strategies. A lot of work is done to identify the types of data quality issues occurring in data warehouses and a large number of industry best practices and standards have been laid down to improve data quality. However, not much work is done for continuous data quality management and improvement particularly in customer data domain. This work begins with the identification of 1) various types of data quality errors in a customer-centric financial database that are introduced in an on-going bases 2) identifies the root causes of those error types and 3) the corrective actions. We have also proposed a framework for continuous improvement and governance of EDW that achieves greater levels of traceability and decision making across four different organizational levels- Infrastructure, Operations, Business and Strategy. The database used for this purpose is a real-world EDW which is being fed by multiple legacy source systems that continuously introduce redundant customer instances causing data duplication. To address this problem of duplicated data we have used neural networks for customer classification which ensure
Advisors/Committee Members: Ramnath, Rajiv.
Subjects: Computer Science
More Like This
4.
Ali, Nawab.
Rethinking I/O in High-Performance Computing Environments.
Degree: PhD, Computer Science and Engineering, 2009, Ohio State University
► As the types of problems we solve in high-performance computing and other…
(more)
▼ As the types of problems we solve in high-performance computing and other areas become more complex, the amount of data generated and used is growing at a rapid rate. Today many terabytes of data are common; tomorrow petabytes of data will be the norm. One of the challenges in high-performance computing is to provide applications with high-speed data access in a distributed, heterogeneous environment. In this dissertation we question the existing I/O paradigms in high-performance computing environments and suggest better alternatives across both local and wide-area networks. We propose three different techniques to accommodate the I/O requirements of scientific applications. We present a new design for a high-performance, scalable parallel file system that obviates the need for dedicated I/O and metadata servers by utilizing object-based storage devices. We also propose a new remote I/O paradigm that takes advantage of the increasing popularity of high-speed networks and centralized data repositories to perform I/O over wide-area networks. Furthermore, we present a scalable I/O forwarding framework that bridges the increasing performance gap between the processing power and the I/O subsystems of massively parallel leadership-class machines such as the IBM Blue Gene/P.
Advisors/Committee Members: Sadayappan, P.
Subjects: Computer science
Keywords: High-performance I/O; Parallel file systems; Leadership-class machines; Remote I/O; High-performance computing
More Like This
5.
Ali, Syed Farooq.
Comparative Studies of Contouring Algorithms for Cardiac Image Segmentation.
Degree: MS, Computer Science and Engineering, 2011, Ohio State University
► In the past few decades, cardiac image analysis especially segmentation has been…
(more)
▼ In the past few decades, cardiac image analysis especially segmentation has been a subject of several studies. In its basic form, cardiac image segmentation involves identifying heart or any of its anatomically or physiologically relevant features from 2D or 3D images. Methods for cardiac image segmentation can be divided into two major categories, namely, low and medium level cardiac segmentation techniques and high level cardiac segmentation techniques also called model based pattern recognition methods. The low and medium level cardiac image segmentation techniques can be further divided into three categories: (a) histogramming and thresholding based cardiac image segmentation techniques, (b) edge based cardiac image segmentation techniques and (c) mathematical morphological approaches for cardiac image segmentation. These approaches suffer from several drawbacks. For example, majority of these techniques are based on thresholding or histogramming and therefore disregard all local features in the image. Prior distribution is not utilized in these approaches. Moreover, these approaches do not include hand-drawn techniques of cardiac segmentation and hence, the concept of fitting mathematical equations to justify the approach does not exist. Model based pattern recognition methods include learning-based techniques and methods involving energy minimization. These methods can overcome the shortcomings encountered in low and medium level segmentation techniques. These approaches do not require thresholding and priors can be estimated from the measured images. The aim of this thesis is to not only review the previous work related to cardiac image segmentation but also implement and compare results from several state-of-the-art segmentation techniques, namely, cardiac contour initialization using morphological operators, cardiac segmentation using snakes (active contour) and its extensions, and STACS (stochastic active contour scheme). These approaches are described in more detail in Chapter 3. In conclusion, cardiac image segmentation remains an active area of research. Further developments, especially to improve robustness, are required to broaden the applicability of these techniques for medical imaging data. Further exploration of model based pattern recognition methods may provide more consistent and accurate results.
Advisors/Committee Members: Machiraju, Raghu.
Subjects: Bioinformatics; Biomedical Engineering; Biomedical Research; Computer Science; Medical Imaging
Keywords: Cardiac MRI segmentation, MRI segmentation, cardiac segmentation, left ventricle MRI segmentation, Contouring algorithms for cardiac image segmentation
More Like This
6.
Ali, Zoya.
Designing Object Oriented Software Applications within the Context of Software Frameworks.
Degree: MS, Computer Science and Engineering, 2011, Ohio State University
► Object-oriented software design and programming is an essential part of a computer…
(more)
▼ Object-oriented software design and programming is an essential part of a computer science curriculum. The idea behind object-oriented design is that because programs are intended to solve problems in the real world, basing software components on real world entities will make the analysis and design of software easier. In the existing Computer Science (CS) curricula that we have examined, we have found that object-oriented concepts are taught with the intent of towards developing software directly using an object-oriented language – such as C++, Java, or C#. However, most software of any consequence is rarely developed directly using a programming language. Most current commercial software is developed using software frameworks, by extending and customizing the default, generic, functionality that frameworks provide. As a consequence, we have observed that novice software developers (such as fresh college graduates) who have been taught object-oriented design, are able to apply good design principles in theory, but rarely in professional practice, in which they are asked to design software intended to run inside a software framework, such as .NET, J2EE, or the Android SDK. In fact, we observe that even software developers, who are not novices, often abandon good design practices when developing software while using a framework, and tend to focus their entire energy on simply “making it work”. In this thesis we attempt to address the above problems. We provide a methodology to teach object-oriented design and implementation for frameworks. We have developed and illustrated this approach using examples drawn from real projects. We show how design patterns can serve as the bridge between the paradigms imposed by the framework and the ideal, unconstrained design of the system. We show through evaluation that the students have positive attitudes towards this methodology, and that designs that have been done by students using this methodology are better than those done without using the methodology. We also illustrate that the students begin to get useful insights about the framework itself.
Advisors/Committee Members: Ramnath, Rajiv.
Subjects: Computer Science
Keywords: Android, J2EE, Design Patterns
More Like This
7.
Apaydin, Tan.
Query Support for Multi-Dimensional and Dynamic Databases.
Degree: PhD, Computer Science and Engineering, 2008, Ohio State University
► In this PhD dissertation, we propose database solutions to support a set…
(more)
▼ In this PhD dissertation, we propose database solutions to support a set of queries for large scale, multidimensional and dynamic databases. In particular, we discuss two main topics: Angular Similarity Queries and Bitmap Indexes.We start with presenting the notion of Angular Similarity that previously lack the database support and discuss our index structures suited for that kind of queries. These proposed compression-based methods enable the angular queries to run faster than the current practice. Cosine, correlation coefficient, and inner product are examples of distance measures utilized as angular similarities. These measures find applications in astrophysics, aviation, graphics, text documents, time series, etc. Then we focus on Bitmap Indexes, which are widely used in data warehouses, scientific applications and which are also implemented by commercial database products such as Oracle. We investigate the Bitmap Indexes from three different perspectives. First, we present our approximate encoding scheme for these indexes. Second, we investigate the data ordering techniques and study their effectiveness on the compression ratios of bitmap indexes. We provide theoretical foundations and a performance analysis on two popular ordering techniques, namely lexicographical ordering and Gray code ordering. Our analysis does not only focus on bitmaps, but from a wider perspective, we cover these approaches in the context of Boolean matrices and binary data. Third, we explore the dynamic nature of real data sets. By exploiting the append-only trend in data warehouses and scientific data sets, we propose a dynamic organization technique for bitmap indexes. For static data sets, compression is shown to be greatly improved by data ordering techniques. However, these data reorganization methods are not applicable to dynamic and very large data sets because of their significant overhead. Our dynamic data structure and the algorithm for organizing the bitmap indexes provide better compression and query processing performance. Our scheme enforces a compression rate close to the optimum for a target ordering of the data which results in fast query response time.
Advisors/Committee Members: Ferhatosmanoglu, Hakan.
Subjects: Computer science
Keywords: Angular Similarity, Bitmap Index, Multidimensional data, Large Scale, Point and Range Queries, Query Execution
More Like This
8.
Asur, Sitaram.
A Framework for the Static and Dynamic Analysis of Interaction Graphs.
Degree: PhD, Computer Science and Engineering, 2009, Ohio State University
► Data originating from many different real-world domains can be represented meaningfully as…
(more)
▼ Data originating from many different real-world domains can be represented meaningfully as interaction networks. Examples abound, ranging from gene expression networks to social networks, and from the World Wide Web to protein-protein interaction networks. The study of these complex networks can result in the discovery of meaningful patterns and can potentially afford insight into the structure, properties and behavior of these networks. Hence, there is a need to design suitable algorithms to extract or infer meaningful information from these networks. However, the challenges involved are daunting. First, most of these real-world networks have specific topological constraints that make the task of extracting useful patterns using traditional data mining techniques difficult. Additionally, these networks can be noisy (containing unreliable interactions), which makes the process of knowledge discovery difficult. Second, these networks are usually dynamic in nature. Identifying the portions of the network that are changing, characterizing and modeling the evolution, and inferring or predicting future trends are critical challenges that need to be addressed in the context of understanding the evolutionary behavior of such networks. To address these challenges, we propose a framework of algorithms designed to detect, analyze and reason about the structure, behavior and evolution of real-world interaction networks. The proposed framework can be divided into three components: 1. A static analysis component where we propose efficient, noise-resistant algorithms taking advantage of specific topological features of these networks to extract useful functional modules and motifs from interaction graphs. 2. An event detection component where we propose algorithms to detect and characterize critical events and behavior for evolving interaction graphs 3. A temporal reasoning component where we propose approaches wherein one can make useful inferences on events, communities, individuals and their interactions over time. For each component, we propose either new algorithms, or suggest ways to apply existing techniques in a previously-unused manner. Where appropriate, we compare against traditional or accepted standards. We evaluate the proposed framework on real datasets drawn from clinical, biological and social domains.
Advisors/Committee Members: Parthasarathy, Srinivasan.
Subjects: Computer science
Keywords: data mining, interaction graphs
More Like This
9.
Bai, Xiaole.
Optimal Connected Coverage for Wireless Sensor Networks.
Degree: PhD, Computer Science and Engineering, 2009, Ohio State University
► Coverage and connectivity are two key properties of wireless networks, particularly wireless…
(more)
▼ Coverage and connectivity are two key properties of wireless networks, particularly wireless sensor networks (WSNs). Deploying sensor nodes to simultaneously achieve coverage and connectivity requirements is a fundamental problem in WSNs. It is insufficient to consider coverage alone when deploying a wireless sensor network; connectivity must also be considered. While moderate loss of coverage can be tolerated by WSN applications, loss of connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not sufficient for a wireless sensor network to just be connected, it should be k-connected (for k > 1). In this dissertation, we propose optimal deployment patterns to achieve both full coverage and k-connectivity for k=1,2,3,4,5, and 6, respectively, and prove their optimality for all values of rc/rs, where rc is the communication radius and rs is the sensing radius. By optimal deployment patterns, we mean those patterns that can achieve desired coverage and connectivity requirements with the fewest sensor nodes. Our results’ fundamentality and generality facilitate their practical applications in, e.g., wireless mesh networks and 802.15.4 networks. We discover an interesting pattern mutation phenomenon in pattern evolution as rc/rs continuously changes. This phenomenon has both theoretical and practical implications. We also study several practical issues in wireless sensor network deployment in this dissertation.
Advisors/Committee Members: Xuan, Dong.
Subjects: Computer science
More Like This
10.
Balaraman, Subha.
Bill Share - Capacity Planning and Management.
Degree: MS, Computer Science and Engineering, 2012, Ohio State University
► Management of the information technology of today's enterprise must address the twofold…
(more)
▼ Management of the information technology of today's enterprise must address the twofold challenge of meeting customer expectations on one hand while staying competitive by controlling IT costs on the other hand. Round-the-clock performance, availability and security are the crucial indicators of quality of service for mission critical web applications. Tradeoffs are necessary to accommodate hardware limitations, quality issues and budget concerns. Capacity planning techniques are essential for ensuring the quality of web services within budget. In particular, with multi-tier architectures becoming industry standards, it is important to design effective and accurate performance prediction models under an enterprise production environment with a real workload mix. The primary objective of the research described in this thesis is to understand the techniques for capacity planning within an enterprise organization when a significant new service is integrated. We first propose a new online service component named Bill Share and then describe how this service integrates with other existing web services of the enterprise. To provide a new service that results in an increase in sales resulting in further profits. We then perform capacity modeling with different hardware models and evaluate the performance metrics against a similar bill tracking web application. We then build an application prototype to validate response times, availability and server utilization's predicted by our model.
Advisors/Committee Members: Ramnath, Rajiv.
Subjects: Computer Engineering; Computer Science
Keywords: capacity planning; virtualization; capacity management; bill sharing; loadrunner; capacity modeling
More Like This
11.
Balasubramanian, Deepan Karthik.
Efficient Sparse Matrix Vector Multiplication for Structured Grid Representation.
Degree: MS, Computer Science and Engineering, 2012, Ohio State University
► Due to technology advancements, there is a need for higher accuracy in…
(more)
▼ Due to technology advancements, there is a need for higher accuracy in the scientic computations. Sparse matrix-vector (SpMV) multiplication is a widely used kernel in scientic applications. There can be significant performance variablility due to irregular memory access patterns. There is a great opportunity to optimize these applications. Conventional algorithms needs to be modied to take advantage of these improved architecture. In the first part of the thesis, we focus on introducing new data structure, Block Structured Grid, that allows vectorization. We also focus on modifying the the existing Block CSR representation of structured grids to improve the performance. Due to the inherent nature of structured grid problems, which uses block elements due to the degrees of freedom involved in the problem, blocked structures are considered for improving the performance. We compare our performance with existing standard algorithms in PETSc. With the new matrix representations we were able to achieve an average of 1.5x performance improvement for generic algorithms. In the second part of the thesis, we compare the performance of PFlotran, an application for modeling Multiscale-Multiphase-Multicomponent Subsurface Reactive Flows, using Block Structured Grid and Vectorized Block CSR against standard matrix representations against standard data structures. With the new matrix representations we were able to achieve an average of 1.2x performance improvement.
Advisors/Committee Members: Ponnuswamy, Dr.Sadayappan.
Subjects: Computer Engineering; Computer Science
More Like This
12.
Bas, Erdeniz Ozgun.
Load-Balancing Spatially Located Computations using Rectangular Partitions.
Degree: MS, Computer Science and Engineering, 2011, Ohio State University
► Distributing spatially located heterogeneous workloads is an important problem in parallel scientific…
(more)
▼ Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. Particle-in-cell simulators, ray tracing and partial differential equations are some of the applications with spatially located workload. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Balancing the load does not guarantee to minimize the total runtime of an application. In order to achieve that, one must also take into account the communication cost. Rectangle shaped partitioning inherently keeps communications small, yet one should proactively minimize them. The algorithms we propose are tested in simulation on a wide set of instances and compared to state of the art algorithm. Results show that m-way jagged partitions are low in total communication cost and practical to use.
Advisors/Committee Members: Catalyurek, Umit V.
Subjects: Computer Science
Keywords: matrix partitioning; load balancing; rectangular partitioning; scientific computing; high performance computing; parallel computing
More Like This
13.
Baskaran, Muthu Manikandan.
Compile-time and Run-time Optimizations for Enhancing Locality and Parallelism on Multi-core and Many-core Systems.
Degree: PhD, Computer Science and Engineering, 2009, Ohio State University
► Current trends in computer architecture exemplify the emergence of multiple processor cores…
(more)
▼ Current trends in computer architecture exemplify the emergence of multiple processor cores on a chip. The modern multiple-core computer architectures that include general-purpose multi-core architectures (from Intel, AMD, IBM, and Sun), and specialized parallel architectures such as the Cell Broadband Engine and Graphics Processing Units (GPUs) have very high computation power per chip. A significant challenge to be addressed in these systems is the effective load-balanced utilization of the processor cores. Memory subsystem has always been a performance bottleneck in computer systems and it is more so, with the emergence of processor subsystem with multiple on-chip processor cores. Effectively managing the on-chip and off-chip memories and enhancing data reuse to maximize memory performance is another significant challenge in modern multiple-core architectures. Our work addresses these challenges in multi-core and many-core systems, through various compile-time and run-time optimization techniques. We provide effective automatic compiler support for managing on-chip and off-chip memory accesses, with the compiler making effective decisions on what elements to move in and move out of on-chip memory, when and how to move them, and how to efficiently access the elements brought into on-chip memory. We develop an effective tiling approach for mapping computation in regular programs on to many-core systems like GPUs. We develop an automatic approach for compiler-assisted dynamic scheduling of computation to enhance load balancing for parallel tiled execution on multi-core systems. There are various issues that are specific to the target architecture which need attention to maximize application performance on the architecture. First, the levels of parallelism available and the appropriate granularity of parallelism needed for the target architecture have to be considered while mapping the computation. Second, the memory access model may be inherent to the architecture and optimizations have to be developed for the specific memory access model. We develop compile-time transformation approaches to address performance factors related to parallelism and data locality that are GPU architecture-specific, and develop an end-to-end compiler framework for GPUs.
Advisors/Committee Members: Ponnuswamy, Sadayappan.
Subjects: Computer science
Keywords: Compilers. Multi-cores, GPUs
More Like This
14.
Bernard Selvaraj, Anand Joseph.
Effects of Loop Tiling using Primetile and Dyntile.
Degree: MS, Computer Science and Engineering, 2010, Ohio State University
► Loop tiling is one of the most important compiler optimization techniques. A…
(more)
▼ Loop tiling is one of the most important compiler optimization techniques. A multilevel tiled code can improve the running time of the program by maximizing data reuse.PrimeTile and DynTile are tools that are used to generate parametrized multi-level tiledcode. The tile size parameters need not be specified during compilation. This enables runtime optimization of the program The values assigned to the tile size parameters influence the running time of the program. The choice of the tile size parameters play an important role in the running time of the program. After generating the multi-level tiled code, it would be ideal to set the tile size parameters to the values that would give the best running time for all the valid permutations of the tile size parameters. In a multi-level tiled code there are several valid permutations for the tile size parameters and hence the search space is huge. An exhaustive search through all the valid permutations defeats the purpose of the search because the time taken for such a search would be much longer than the execution time of the program. This calls for redefining the problem. After generating the multi-level tiled code, the tile size parameters should be set to the values that give an execution time that is very close to the best running time for all the valid permutations for the tile sizes. To suggest a good search method to find the required tile size parameters, it is necessary to perform an exhaustive study over the effects on the running time of the program by changing the tile size parameters. This study must be done over different benchmarks. The tests are done on tiled loops generated by PrimeTile and DynTile. The characteristics of the tiled loops generated by PrimeTile are compared with the tiled loops generated by DynTile. The effects of vectorization on these tiled loops are also studied.
Advisors/Committee Members: Sadayappan, Ponnusamy.
Subjects: Computer science
Keywords: Loop Tiling; Primetile; Dyntile
More Like This
15.
Bharathan, Vivek.
Belief Revision in Dynamic Abducers through Meta-Abduction.
Degree: MS, Computer Science and Engineering, 2010, Ohio State University
► Abduction machines (or abducers) infer to the best explanation for the data…
(more)
▼ Abduction machines (or abducers) infer to the best explanation for the data presented to them, and may accumulate beliefs (the conclusions of the inferences) about the world. An abducer’s beliefs are justified as being the best explanation in contrast with alternative hypotheses. However, the best explanation available to (achievable by) an abducer need not be the true explanation for a variety of reasons including: incomplete search for alternative explanations, insufficient data, and inadequate background knowledge for evaluating alternatives. In light of this fallibility, algorithms were investigated for detecting and correcting errors, for dynamic abducers, by comparing a range of alternative algorithms with regard to effectiveness and computational costs. Dynamic abducers interpret an incoming information stream by producing their best explanations at any point in time. They accumulate new beliefs, and update older beliefs, in the light of new information. In the present work, algorithms were developed for detecting and correcting errors in the accumulated beliefs of such abducers. These algorithms treat the problem of identifying errors as meta-abduction, where certain anomalies that occur during processing are explained as resulting from specific mistakes in previous abductive processing. Errors are then corrected, and beliefs revised, by adopting alternative explanations. A brute-force algorithm for this meta-abduction is computationally intractable, so heuristics were developed with prospects of improving performance. Since a priori mathematical analysis of the algorithms using these heuristics did not reveal useful bounds, simulation experiments were conducted, using a specimen domain. The domain was that of multi-object tracking, where an abduction machine, over time, attempts to maintain the track history of mobile entities, based on sensor reports. The experimental results suggest that, using only the heuristics that were investigated, belief revision by meta-abduction enables only small improvements in correctness, and is computationally expensive.
Advisors/Committee Members: Josephson, John.
Subjects: Artificial intelligence; Computer science
Keywords: Artificial Intelligence, Abductive Inference, Belief Revision, Entity Tracking
More Like This
16.
Bicer, Tekin.
Supporting Fault Tolerance and Dynamic Load Balancing in FREERIDE-G.
Degree: MS, Computer Science and Engineering, 2010, Ohio State University
► Over the last 2-3 years, the importance of data-intensive computing has increasingly…
(more)
▼ Over the last 2-3 years, the importance of data-intensive computing has increasingly been recognized, closely coupled with the emergence and popularity of map-reduce for developing this class of applications. Besides programmability and ease of parallelization, fault tolerance and load balancing are clearly important for data-intensive applications, because of their long running nature, and because of the potential for using a large number of nodes for processing massive amounts of data. Two important goals in supporting fault-tolerance are low overheads and efficient recovery. With these goals, our work proposes a different approach for enabling data-intensive computing with fault-tolerance. Our approach is based on an API for developing data-intensive computations that is a variation of map-reduce, and it involves an explicit programmer-declared reduction object. We show how more efficient fault-tolerance support can be developed using this API. Particularly, as the reduction object represents the state of the computation on a node, we can periodically cache the reduction object from every node at another location and use it to support failure-recovery. Supporting dynamic load balancing in heterogeneous environments, such as grids, is another crucial problem. Successfully distributing the tasks among the processing units according to their processing capabilities, and during this process minimizing the overhead of the system are significant to the overall execution. Our approach is based on the independent data elements which can be processed by any processing resource in the system. We evaluated and showed how effectively our dynamic load balancing system can perform with our data-intensive computing API. Specifically, the problem space that our API is working on enables us to process data elements independently. This property can be exploited, and any data element in the system can be assigned to any computational resource during the execution. We have extensively evaluated our approaches using two data-intensive applications. Our results show that the overheads of our schemes are extremely low. Furthermore, we compared our fault tolerance approach with one of the Map-Reduce implementations, Hadoop. Our fault tolerance system outperforms Hadoop both in absence and presence of failures.
Advisors/Committee Members: Agrawal, Gagan.
Subjects: Computer science; Information Systems; Systems design
Keywords: Fault tolerance; Load balancing; Data-intensive computing; Cloud computing; Map-reduce
More Like This
17.
Boggus, Matthew J.
Modeling, Evaluation, Editing, and Illumination of Three Dimensional Mazes and Caves for Computer Games.
Degree: PhD, Computer Science and Engineering, 2012, Ohio State University
► Caves are commonly used as environments in computer games. As the popularity…
(more)
▼ Caves are commonly used as environments in computer games. As the popularity of open world games rises, so does the demand for expansive virtual environments. To ease this cost, many tools have been developed to create and edit content for games including terrain, plants, roads, buildings, and cities. The same is not true for caves. We present data structures and algorithms to create, evaluate, edit, and illuminate three dimensional models of caves for use in computer games. Game levels can be classified according to their spatial configuration: linear, maze, or open. Caves formed by the same geological process have similar features. These define parameters that can be used to partially or fully automate the creation of cave models of different spatial configurations. Additional information about the model such as its volume, number of branching paths, and number of connected components can be used by the designer in evaluating and editing the model to meet gameplay requirements. To assist in editing of cave models we propose a new data structure and framework and compare its use to existing modeling approaches. Physically based illumination of a cave typically results in low level lighting which is not suitable for games. We introduce a new illumination model based on radiant flux that can be used to ensure a sufficient amount of light is present throughout the cave. The new illumination model can also be adapted to assist in player navigation. Illuminating a scene according to distance to objects within it creates highlights that captures the player’s visual attention. A user study was done to evaluate the new technique.
Advisors/Committee Members: Crawfis, Roger.
Subjects: Computer Science
Keywords: computer graphics; computer games; caves; mazes; game level evaluation; game level illumination
More Like This
18.
Bokhari, Saniyah S.
Parallel Solution of the Subset-sum Problem: An Empirical Study.
Degree: MS, Computer Science and Engineering, 2011, Ohio State University
► We investigate the parallelization of an algorithm on three very different architectures.…
(more)
▼ We investigate the parallelization of an algorithm on three very different architectures. These are: a 128-processor Cray XMT massively multithreaded machine, a 16-processor IBM x3755 shared memory machine and a 240-core NVIDIA FX 5800 graphics processor unit (GPU). The problem we use in our investigation is the well-known subset-sum problem. While this is known to be NP-complete, it is solvable in pseudo-polynomial time, i.e., time proportional to the number of input objects multiplied by the sum of their sizes. This product defines the size of the dynamic programming table used to solve the problem. The hypothesis that we wish to test is that the Cray, with its specialized hardware and large uniform shared memory, is suitable for very large problems, the IBM x3755 is suitable for intermediate sized problems and the NVIDIA FX 5800 can give superior performance only for problems that fit within its modest internal memory. We show that it is straightforward to parallelize this algorithm on the Cray XMT primarily because of the word-level locking that is available on this architecture. For the other two machines we present an alternating word algorithm that can implement an efficient solution. The timings of our respective codes were carefully measured over a comprehensive range of problem sizes. On the Cray XMT we observe very good scaling for large problems and see sustained performance as the problem size increases. However this machine has poor scaling for small problem sizes; it performs best for problem sizes of 1012 bits or more. The IBM x3755 performs very well on medium sized problems, but has poor scalability as the number of processors increases and is unable to sustain performance as the problem size increases. This machine tends to saturate for problem sizes of 1011 bits. The NVIDIA GPU performs well for problems whose tables t within its 4GB device memory. This corresponds to tables of size approximately 1010/. The experimental measurements support our hypothesis and show that each machine gives superior performance for distinct ranges of problem sizes and demonstrate the strengths and weaknesses of the three architectures.
Advisors/Committee Members: Lai, Ten H.
Subjects: Computer Engineering; Computer Science
Keywords: Cray XMT; Dynamic Programming; IBM x3755; Multicore; Multithreading; NVIDIA FX 5800; OMP; Opteron; Parallel Algorithms; Parallel Computing; Shared Memory; Subset-sum problem
More Like This
19.
Bolinger, Joe William.
Micro-Modeling: A Visual Design Framework for Collaborative Tools in Complex Service Organizations.
Degree: PhD, Computer Science and Engineering, 2011, Ohio State University
► Collaborative software plays an important role in firms that rely on teams…
(more)
▼ Collaborative software plays an important role in firms that rely on teams to work together effectively and in pursuit of a common goal. They allow individuals to interact with one another in ways that were not previously possible, and as mediators of social interactions they have the potential to make an organization’s people-driven operations more visible and improve the self-management practices of teams. However, collaborative technologies have never fully realized their potential as tools for sustaining strategic self-management activities. Technology users tend to ignore features that are not directly related to their immediate day-to-day tasks, and they are often unwilling to deal with more complex interfaces or to input additional data into a system even if it would be beneficial from a collective organizational perspective. This research examines the often-conflicting relationship between the needs of individuals and groups in computer supported cooperative work (CSCW) systems and it addresses the lack of established design principles for resolving the tradeoffs that they create in practice. Two contributions are made. First, a set of design guidelines is proposed for building collaborative software systems that can collect useful metadata from a managerial point of view in a way that is transparent to end-users. These guidelines help ensure that technology can support group-level needs, such as self-governance and self-monitoring, without requiring individual end-users to input data or perform actions that have no clear and immediate value to them. These principles are first developed through a critical examination of two divergent areas in the literature and are subsequently assembled into a single software interface design pattern. Next, the pattern is used to develop a prototype system that is evaluated through a naturalistic user study. The results of this study provide evidence that user interfaces can be intentionally designed to capture strategically oriented metadata, and that it can be done in ways that are not perceived as distracting or irrelevant by individual end-users. However, the study also revealed that further research is needed to develop a related set of strategies for more effectively directing any collected metadata to people in ways that will encourage bottom-up self-management activities to occur. Second, a novel research methodology is presented to coordinate this body of research. The presence of relevant, but often idiosyncratic, sociocultural influences makes objectively evaluating forms of collaborative technology a well-known challenge. Subsequently, heuristics and engineering guidelines are common in fields like CSCW because accurately predicting if collaborative technologies will be successful in new domains is difficult. Yet, there are no systematic methods for constructing heuristic knowledge from empirical data. The method proposed here addresses this gap by framing observational techniques from the social sciences within the structural foundation of software design patterns to facilitate an abductive, heuristic-building, research process. While this study illustrates one application of the methodology in practice, further research would be necessary to adequately compare it with traditional approaches.
Advisors/Committee Members: Ramanathan, Jayashree.
Subjects: Computer Engineering; Computer Science
Keywords: CSCW; computer supported cooperative work; collaborative tools; design patterns; groupware; design research
More Like This
20.
Bondhugula, Uday Kumar.
Effective Automatic Parallelization and Locality Optimization Using The Polyhedral Model.
Degree: PhD, Computer Science and Engineering, 2008, Ohio State University
► Multicore processors have now become mainstream. The difficulty ofprogramming these architectures to…
(more)
▼ Multicore processors have now become mainstream. The difficulty ofprogramming these architectures to effectively tap the potential of multiple processing units is well-known. Among several ways of addressing this issue, one of the very promising and simultaneously hard approaches is Automatic Parallelization. This approach does not require any effort on part of the programmer in the process of parallelizing a program. The Polyhedral model for compiler optimization is a powerful mathematical framework based on parametric linear algebra and integer linear programming. It provides an abstraction to represent nested loop computation and its data dependences using integer points in polyhedra. Complex execution-reordering, that can improve performance by parallelization as well as locality enhancement, is captured by affine transformations in the polyhedral model. With several recent advances, the polyhedral model has reached a level of maturity in various aspects – in particular, as a powerful intermediate representation for performing transformations, and code generation after transformations. However, an approach to automatically find good transformations for communication-optimized coarse-grained parallelization together with locality optimization has been a key missing link. This dissertation presents a new automatic transformation framework that solves the above problem. Our approach works by finding good affine transformations through a powerful and practical linear cost function that enables efficient tiling and fusion of sequences of arbitrarily nested loops. This in turn allows simultaneous optimization for coarse-grained parallelism and locality. Synchronization-free parallelism and pipelined parallelism at various levels can be extracted. The framework can be targeted to different parallel architectures, like general-purpose multicores, the Cell processor, GPUs, or embedded multiprocessor SoCs. The proposed framework has been implemented into a new end-to-end transformation tool, PLUTO, that can automatically generate parallel code from regular C program sections. Experimental results from the implemented system show significant performance improvement for single core and multicore execution over state-of-the-art research compiler frameworks as well as the best native production compilers. For several dense linear algebra kernels, code generated from Pluto beats, by a significant margin, the same kernels implemented with sequences of calls to highly-tuned libraries supplied by vendors. The system also allows empirical optimization to be performed in a much wider context than has been attempted previously. In addition, Pluto can serve as the parallel code generation backend for several high-level domain-specific languages.
Advisors/Committee Members: Sadayappan, Prof. P.
Subjects: Computer science
Keywords: Automatic Parallelization; Polyhedral Model; Compiler Optimizations
More Like This
21.
Bronish, Derek.
Abstraction as the Key to Programming, with Issues for Software Verification in Functional Languages.
Degree: PhD, Computer Science and Engineering, 2012, Ohio State University
► Abstraction is our most powerful tool for understanding the universe scientifically. In…
(more)
▼ Abstraction is our most powerful tool for understanding the universe scientifically. In computer science, the term “abstraction” is overloaded, and its referents have not been enunciated with sufficient clarity. A deep understanding of what abstraction is and the different ways it can be employed would do much to strengthen both the research and the practice of software engineering. Specifically, this work focuses on abstraction into pure mathematics as it pertains to the intellectual complexity of computer programming. A Grand Challenge for software engineering research is to develop a verifying compiler, which takes as input a computer program and a rigorous specification of its intended behavior, and which only generates an executable if the code is proven correct via automated reasoning. The hypothetical verifying compiler would radically change the face of technology by guaranteeing that code always behaves as it should. We investigate the ways in which good abstractions, maximally exploited, can make this dream a reality. This document presents, at varying levels of technical detail, evidence for the utility of abstractions in software. We show how standard approaches to programming, even in the realm of “formal methods,” lack full abstraction. We argue that data abstraction should be achieved via purely mathematical modeling, and that this approach enables modular, scalable verification of complete system behavior. We also warn that a programming language’s formal semantics can dramatically impact the feasibility of a verifying compiler for that language. One of our main results is that the class of “functional” programming languages cannot be soundly verified by the pervasive existing methods due to an insidious and subtle issue related to data abstraction and relational specifications. We build on this unsoundness proof by sketching a new solution, and fragments of a new functional programming language that incorporates it.
Advisors/Committee Members: Weide, Dr. Bruce W.
Subjects: Computer Engineering; Computer Science
Keywords: software verification; programming languages; abstraction
More Like This
22.
Busaryev, Oleksiy.
On Computing and Tracking Geometrical and Topological Features.
Degree: PhD, Computer Science and Engineering, 2012, Ohio State University
► In scientific research and industrial applications, the questions of computing, characterizing and…
(more)
▼ In scientific research and industrial applications, the questions of computing, characterizing and tracking important features in the input data arise with noticeable frequency. Feature detection is a critical step in automated data processing such as mesh generation. In high-dimensional data analysis, there is a strong demand for feature classification and tracking methods. Finally, in scientific visualization and simulation of real-world phenomena, modeling small-scale features is often essential for visual realism. All these questions motivated a substantial amount of research in geometric modeling, computational geometry, computational topology and computer animation. The first topic we investigate in regard to these questions is feature processing for automated mesh generation. Specifically, for a shape provided as a collection of possibly improperly meeting and/or self-intersecting patches, we construct a watertight mesh that has many of these representation errors fixed. To achieve that, we augment the existing Delaunay meshing algorithm for piecewise smooth domains with a preprocessing step that recomputes the 1-skeleton of the complex, producing a valid input for the mesher. For shapes provided in the form of a point cloud data, researchers are often interested in analyzing high-level features, which are traditionally computed using topological methods from simplicial complexes built on top of the point clouds. This motivates the second topic of our research: geometrical and topological queries on arbitrary simplicial complexes. The first problem we tackle is maintaining geometry-aware homological features under changes in the underlying simplicial complex. We capitalize on the theory of persistent homology, which provides a principled way to describe features. Building upon the existing matrix framework, we propose a method for tracking a chosen generator so that it undergoes only local changes. Another question we address is speeding up miscellaneous queries about the homology of a simplicial complex. We annotate the simplices of the complex with binary signatures that allow efficient characterizations of homology cycles. Using this method, we improve the running time of existing algorithms for computing a shortest homology basis and the shortest cycle in a homology class in 1-dimensional homology. We also provide a more implementation-friendly annotation algorithm, which, though having a worse running time, blends nicely into the persistence homology theory and can be considered as a generalization of the persistence algorithm. The final topic of our research in regards to geometric features is relatively independent of the previous two. We switch our attention to the field of physically-based simulation of natural phenomena and present methods to realistically model small-scale features that improve the simulation realism. Our contribution is the physical model for bubbles in a liquid foam. We propose to approximate the foam structure using a space-filling diagram, which allows us to easily infer connectivity between bubbles and efficiently simulate their interaction, handling foam behaviour such as coalescing and instability of multi-bubble clusters. We demonstrate efficiency of our approach by providing simulation examples that plausibly imitate real-world bubble effects.
Advisors/Committee Members: Dey, Tamal K.
Subjects: Computer Science
Keywords: geometric modeling; computational topology; physically-based simulation
More Like This
23.
Cai, Da.
Analysis and Evaluation of an Integrated Web Services Framework.
Degree: MS, Computer Science and Engineering, 2012, Ohio State University
► Along with increasing demands for using software to deal with model simulation…
(more)
▼ Along with increasing demands for using software to deal with model simulation and physical predictor in industry, professional people prefer to choose an effective and efficient way to achieve their goals, using professional software applications. It is necessary to provide a simple way for users to access on-demand software services without having to configure and maintain it by themselves. In this thesis, I propose a web-based framework to integrate multiple software applications for users to access their required software services through E-Commerce, and I show the benefits of this service-oriented architecture. We use two typical “Simulation Software as a Service” (SMaaS) implementations to illustrate how this integrated framework can be implemented, and make surveys for users to evaluate the user experience.
Advisors/Committee Members: Ramnath, Rajiv.
Subjects: Computer Science
Keywords: Web service; Software as a Service; Single sign on; E-Commerce
More Like This
24.
Canahuate, Guadalupe M.
Enhanced Bitmap Indexes for Large Scale Data Management.
Degree: PhD, Computer Science and Engineering, 2009, Ohio State University
► Advances in technology have enabled the production of massive volumes of data…
(more)
▼ Advances in technology have enabled the production of massive volumes of data through observations and simulations in many application domains.These new data sets and the associated queries pose a new challenge for efficient storage and data retrieval that requires novel indexing structures and algorithms. We propose a series of enhancements to bitmap indexes to make them account for the inherent characteristics of large scale datasets and to efficiently support the type of queries needed to analyze the data. First, we formalize how missing data should be handled and how queries should be executed in the presence of missing data. Then, we propose an adaptive code ordering as a hybrid between Gray code and lexicographic orderings to reorganize the data and further reduce the size of the already compressed bitmaps. We address the inability of the compressed bitmaps to directly access a given row by proposing an approximate encoding that compresses the bitmap in a hash structure. We also extend the existing run-length encoders of bitmap indexes by adding an extra word to represent future rows with zeros and minimize the insertion overhead of new data. We propose a comprehensive framework to execute similarity searches over the bitmap indexes without changes to the current bitmap structure, without accessing the original data, and using a similarity function that is meaningful in high dimensional spaces. Finally, we propose a new encoding and query execution for non-clustered bitmap indexes that combines several attributes in one existence bitmap, reduces the storage requirement, and improves query execution and update time for low cardinality attributes.
Advisors/Committee Members: Hakan, Ferhatosmanoglu.
Keywords: bitmap index; scientific data management; large scale indexing
More Like This
25.
Chai, Lei.
High Performance and Scalable MPI Intra-node Communication Middleware for Multi-core Clusters.
Degree: PhD, Computer Science and Engineering, 2009, Ohio State University
► Cluster of workstations is one of the most popular architectures in high…
(more)
▼ Cluster of workstations is one of the most popular architectures in high performance computing, thanks to its cost-to-performance effectiveness. As multi-core technologies are becoming mainstream, more and more clusters are deploying multi-core processors as the build unit. In the latest Top500 supercomputer list published in November 2008, about 85% of the sites use multi-core processors from Intel and AMD. Message Passing Interface (MPI) is one of the most popular programming models for cluster computing. With increased deployment of multi-core systems in clusters, it is expected that considerable communication will take place within a node. This suggests that MPI intra-node communication is going to play a key role in the overallapplication performance. This dissertation presents novel MPI intra-node communication designs, including user level shared memory based approach, kernel assisted direct copy approach, and efficient multi-core aware hybrid approach. The user level shared memory based approach is portable across operating systems and platforms. The processes copy messages into and from a shared memory area for communication. The shared buffers are organized in a way such that it is efficient in cache utilization and memory usage. The kernel assisted direct copy approach takes help from the operating system kernel and directly copies message from one process to another so that it only needs one copy and improves performance from the shared memory based approach. In this approach, the memory copy can be either CPU based or DMA based. This dissertation explores both directions and for DMA based memory copy, we take advantage of novel mechanism such as I/OAT to achieve better performance and computation and communication overlap. To optimize performance on multi-core systems, we efficiently combine the shared memory approach and the kernel assisted direct copy approach and propose a topology-aware and skew-aware hybrid approach. The dissertation also presents comprehensive performance evaluation and analysis of the approaches on contemporary multi-core systems such as Intel Clovertown cluster and AMD Barcelona cluster, both of which are quad-core processors based systems. Software developed as a part of this dissertation is available in MVAPICH and MVAPICH2, which are popular open-source implementations of MPI-1 and MPI-2 libraries over InfiniBand and other RDMA-enabled networks and are used by several hundred top computing sites all around the world.
Advisors/Committee Members: Panda, Dhabaleswar.
Subjects: Computer science
Keywords: MPI; Cluster Computing; Multi-core Processors
More Like This
26.
Chanamolu, Yashwanth.
An Orientation based Image CAPTCHA.
Degree: MS, Computer Science and Engineering, 2009, Ohio State University
► CAPTCHA is now almost a standard security technology, and has found widespread…
(more)
▼ CAPTCHA is now almost a standard security technology, and has found widespread application in commercial websites. To date, almost all CAPTCHA designs are labeling based. Labeling based CAPTCHAs refer to those that make judgment based on whether the question “what is it?” has been correctly answered. Essentially in Artificial Intelligence (AI), this means judgment depends on whether the new label provided by the user side matches the label already known to the server. Labeling based CAPTCHA designs have some common weaknesses that can be taken advantage of attackers. First, the label set, i.e., the number of classes, is small and fixed. Due to deformation and noise in CAPTCHAs, the classes have to be further reduced to avoid confusion. Second, clean segmentation in current design, in particular character labeling based CAPTCHAs, is feasible. Sometimes, it is even trivial. The state of the art of CAPTCHA design suggests that the robustness of character labeling schemes should rely on the difficulty of finding where the character is (segmentation), rather than which character it is (recognition). However, the shapes of alphabet letters and numbers have very limited geometry characteristics that can be used by humans to tell them yet are also easy to be indistinct. The major contribution of this thesis is that we propose a new direction in CAPTCHA design by focusing on orientation rather than labeling. We introduce an orientation based image CAPTCHA which uses an image set which gets dynamically updated. By focusing on orientation we eliminate problems facing labeling based CAPTCHAs like limited label classes and object recognition. We built a CAPTCHA web application using Java Sever Pages technology and used AJAX techniques to make the user interface more interactive and user friendly. We deployed our application on a web server and tabulated the response time and success ratio results we got.
Advisors/Committee Members: Xuan, Dong.
More Like This
27.
Chandran, Varadharajan.
Robust Method to Deduce Cache and TLB Characteristics.
Degree: MS, Computer Science and Engineering, 2011, Ohio State University
► Modern compilers of self-optimizing computing systems require the values of hardware parameters…
(more)
▼ Modern compilers of self-optimizing computing systems require the values of hardware parameters such as the capacity of cache and number of entries in translation lookaside buffer (TLB). Additional information such as the cache block size and page size along with the Hit Time and Miss Penalty of these hardware entities are needed to apply static and dynamic compiler optimization techniques. Currently, no tool or approach is robust enough to provide accurate information regarding the underlying hardware. They fail when encoutering multiple levels of cache and TLB present in current generation of processors. In this Thesis, we describe a staggered and robust approach to first detecting the hardware entities and their sizes and then disambiguating between the entities by deducing their block sizes. We describe the novel algorithms for measurement of the hardware parameters and the mathematical intuition behind the disambiguation. Experimental evaluations of this technique on traditional workstations, laptops and servers show that our approach produces more accurate and complete results than existing tools.
Advisors/Committee Members: Sadayappan, Dr. Ponnusamy.
Subjects: Computer Engineering; Computer Science
Keywords: Cache; TLB; Translation Lookaside Buffer; Hardware parameters; Hit time; Miss Penalty
More Like This
28.
Chandrasekaran, Prashanth.
MULTI-RESOLUTION MULTIMEDIA QOE MODELS FOR IPTV APPLICATIONS.
Degree: MS, Computer Science and Engineering, 2009, Ohio State University
► Internet television (IPTV) is rapidly gaining popularity and is being widely deployed…
(more)
▼ Internet television (IPTV) is rapidly gaining popularity and is being widely deployed on the Internet. In order to pro-actively deliver optimum user Quality of Experience (QoE), service providers need to identify network bottlenecks in real-time and assess their impact on the audio and video quality degradation. While doing so, they cannot rely on actual end-users to report their subjective QoE of audio-visual quality. Also, they cannot rely on computationally intensive objective techniques that involve frame-to-frame Peak-Signal-to-Noise Ratio (PSNR) comparisons of original and re-constructed video sequences. In this thesis, psycho-acoustic-visual models that can predict user QoE of multimedia applications in real-time based on online network status measurements are developed and evaluated. These models cater to multi-resolution IPTV applications that include QCIF, QVGA, SD and HD resolutions encoded using popular audio and video codec combinations. On the network side, the models account for jitter and loss levels, as well as router queuing disciplines: Packet-ordered and Time-ordered first-in-first-out (FIFO). The performance of the multi-resolution multimedia QoE models is evaluated in terms of prediction characteristics, accuracy, consistency and speed. The evaluation results demonstrate that the models are pertinent for: (a) continuous multimedia QoE monitoring, and (b) real- time adaptation of system and network resources, in small-to-large scale deployments of IPTV on the Internet.
Advisors/Committee Members: Ramnath, Dr. Rajiv.
Subjects: Computer science
Keywords: IPTV, audiovisual quality, objective QoE metrics, router queuing disciplines, performance sampling
More Like This
29.
Chen, Ai.
Sealing Borders with Wireless Sensors.
Degree: PhD, Computer Science and Engineering, 2009, Ohio State University
► Wireless sensor networks, which have numerous potential applications such as monitoring environment…
(more)
▼ Wireless sensor networks, which have numerous potential applications such as monitoring environment and security detection, are an active research area in recent years. One of the fundamental research issues in wireless sensor networks is coverage, which determines how well an area is monitored by a sensor network. In this dissertation, we study the fundamental coverage problems for the intrusion detection applications such as international border guarding.(Global) barrier coverage is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice. In this dissertation, we introduce the concept of local barrier coverage to address this limitation. Local barrier coverage guarantees the detection of all movements whose trajectory is confined to a slice of the belt region of deployment. We prove that it is possible for individual sensors to locally determine the existence of local barrier coverage. Although local barrier coverage does not deterministically guarantee global barrier coverage, we show that for thin belt regions, local barrier coverage almost always provides global barrier coverage. Sensors may fail due to various reasons such as heat, malicious activity, environmental hazards, and lack of power. As more and more sensors fail, certain desired properties such as barrier coverage will diminish and eventually fall below a desired level. In such a case, the network will have to be repaired. It is therefore desirable to have mechanisms to monitor network properties. In this dissertation, we are interested in measuring the quality of barrier coverage. In the literature, researchers only consider whether or not a sensor network provides barrier coverage. This is equivalent to measuring its quality as either 0 or 1. We believe quality of barrier coverage is not binary and propose a metric for measuring it. If the measured quality is short of a desired value, we further identify all local regions that need to be repaired. We also discuss how to actually repair a region. For some intrusion detection applications, it may be the case that only one direction of crossing (the belt) is illegal. Therefore, we introduce a new coverage model called one-way barrier coverage. We investigate necessary conditions and sufficient conditions for one-way barrier coverage. We then study how to make a sensor network provide one-way barrier coverage with different barrier models or sensor models.
Advisors/Committee Members: Lai, Ten-Hwang.
More Like This
30.
Chen, Feng.
On Performance Optimization and System Design of Flash Memory based Solid State Drives in the Storage Hierarchy.
Degree: PhD, Computer Science and Engineering, 2010, Ohio State University
► As an emerging storage technology, Flash Memory based Solid State Drive (SSD)…
(more)
▼ As an emerging storage technology, Flash Memory based Solid State Drive (SSD) has shown a high potential to fundamentally change the existing Hard Disk Drive (HDD) based storage systems. Unlike conventional magnetic disks, SSD is built on semiconductor chips and has no mechanical components (e.g. rotating disk platters). This architectural difference brings many attractive technical features, such as high random data access performance and low power consumption. Most importantly, these unique features could potentially address the long-existing technical limitations of conventional magnetic disks. Due to this reason, SSD has been called a 'pivotal technology' that may completely revolutionize current computer storage systems. On the other hand, SSD also poses several critical challenges to application and system designers. First, due to divergent internal structures, SSD is fundamentally different from rotating media, although they share the same logical and physical interfaces. To date we still lack an insightful understanding about the performance characteristics of SSDs, both the positive and negative sides, and their implications to application and system designers. In this dissertation, we present a thorough experimental study on the unique features of SSDs. Second, although SSDs have shown a great performance potential, especially for handling small and random data accesses, SSDs are much more expensive than conventional hard disks. Even considering the decreasing price trend, the price gap between SSDs and HDDs will not disappear in the near future and it significantly prevents the wide adoption of SSDs in practice, especially in cost-sensitive commercial systems. In this dissertation we present the design and implementation of a hybrid storage system, called Hystor, which integrates both SSDs and HDDs to provide a cost-efficient solution for commercial applications with minimal change to other system components and applications. Third, a unique merit of SSD is the internal parallelism, which is the key to effectively exploiting the performance potential of SSDs. Unfortunately, the existing literature mostly focuses on addressing the technical limitations of SSDs (e.g. random write issues) and rarely discusses the internal parallelism. In this dissertation, we present our experimental studies on this unique opportunity provided by SSDs. Our study shows that exploiting internal parallelism can bring great performance benefits, but we must also pay attention to some unexpected dynamics. Our case studies in database systems, a typical data-intensive application, indicate that internal parallelism can significantly improve performance of real-world applications, and many existing HDD-based application optimizations need to be revisited.
Advisors/Committee Members: Zhang, Xiaodong.
Subjects: Computer science
Keywords: solid state drive; flash memory; hard disk drive; hybrid storage system
More Like This
[1] [2] [3] [4] [5] [6] [7] [8]
