I/O Efficient Dynamic Data Structures for Longest Prefix Queries

We present an efficient data structure for finding the longest prefix of a query string q in a dynamic database of strings. When the database strings are prefixes of IP-addresses then this is the IP-lookup problem. Our data structure is I/O efficient. It supports a query with a string q using $O(\log_{B}(n)+\frac{|q|}{B})$ I/O operations, where B is the size of a disk block. It also supports an insertion and a deletion of a string q with the same number of I/Os. The data structure requires O(n/B) blocks, and the running time for each operation is O(Blog _B (n)+|q|).     

A Framework for Succinct Labeled Ordinal Trees over Large Alphabets

We consider succinct representations of labeled ordinal trees that support a rich set of operations. Our new representations support a much broader collection of operations than previous work. In our approach, labels of nodes are stored in a preorder label sequence, which can be compressed using any succinct representation of strings that supports \(\mathtt{{access}}\) , \({\mathtt{{rank}}}\) and \(\mathtt{{select}}\) operations. Thus, we present a framework for succinct representations of labeled ordinal trees that is able to handle large alphabets. This answers an open problem presented by Geary et al., which asks for representations of labeled ordinal trees that remain space-efficient for large alphabets. We further extend our work and present the first succinct representations for dynamic labeled ordinal trees that support several label-based operations including finding the level ancestor with a given label.     

List-based Data Structures for Efficient Management of Advance Reservations

Complex eScience and other sophisticated applications in the field of HPC imply new demands that queuing based resource management systems cannot meet. To guarantee Quality of Service and co-allocation in the Grid, planning based resource management systems implementing advance reservation are needed. These systems face new challenges as a planning based management system has to keep track of the jobs and reservations in the future. Additionally, during the negotiation process of incoming reservations, a good overview of the remaining, not-yet reserved capacity is needed—not only for the current allocation, but also for the whole book-ahead time. Therefore, the resource management problem becomes a two dimensional problem for advance reservations in this field. In this paper different data structures are investigated and discussed in order to fit to planning based resource management. As a result the benefits of using lists of resource allocation or free blocks are exposed. This general idea widely used to manage continuous resources is extended to cover not only the resource dimension but also the time dimension. The list of blocks approach is evaluated in a Grid level and a local resource management system for a computing cluster. The extensive simulations showed a better runtime and higher reservation success rate compared with the currently favored approach of a slotted time and the more sophisticated approach based on AVL trees.     

Efficient Learning in Adaptive Processing of Data Structures

Many researchers have explored the use of neural network models for the adaptive processing of data structures. The learning formulation for one of the models is known as the Backpropagation Through Structure (BPTS) algorithm. The main limitations of the BPTS algorithm are attributed to the problems of slow convergence speed and long-term dependency. In this Letter, a novel heuristic algorithm is proposed. The idea of this algorithm is to optimize the free parameters of the node representation in data structure by using a hybrid type of learning algorithm. Encouraging results achieved demonstrate that this proposed algorithm outperforms the BPTS algorithm.     

应用层并行I/O效率研究

针对划分计算空间到多个计算区域(zone)这类问题,采用基于计算区域组织I/O时,首先需选择计算区域的主进程;其次当某一进程是两个计算区域的主进程时需指定计算区域数据访问先后顺序。设计了多级极大独立集算法实现上述过程。该算法利用图论中的连通图以及极大独立集概念规定了每个计算区域进行数据访问的进程以及优先级。经样例分析,采用此种方法达到I/O并行度最高,并实现在并行度最高情况下通信量最小。     

Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems

Following in the spirit of data structure and algorithm correctness checking, authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended, even if the data structure is being controlled by a remote untrusted host.     

Data space mapping for efficient I/O in large multi-dimensional databases

In this paper, we propose data space mapping techniques for storage and retrieval in multi-dimensional databases on multi-disk architectures. We identify the important factors for an efficient multi-disk searching of multi-dimensional data and develop secondary storage organization and retrieval techniques that directly address these factors. We especially focus on high dimensional data, where none of the current approaches are effective. In contrast to the current declustering techniques, storage techniques in this paper consider both inter- and intra-disk organization of the data. The data space is first partitioned into buckets, then the buckets are declustered to multiple disks while they are clustered in each disk. The queries are executed through bucket identification techniques that locate the pages. One of the partitioning techniques we discuss is especially practical for high dimensional data, and our disk and page allocation techniques are optimal with respect to number of I/O accesses and seek times. We provide experimental results that support our claims on two real high dimensional datasets.     

Optimal Data-Space Partitioning of Spatial Data for Parallel I/O

It is desirable to design partitioning methods that minimize the I/O time incurred during query execution in spatial databases. This paper explores optimal partitioning for two-dimensional data for a class of queries and develops multi-disk allocation techniques that maximize the degree of I/O parallelism obtained in each case. We show that hexagonal partitioning has optimal I/O performance for circular queries among all partitioning methods that use convex non-overlapping regions. An analysis and extension of this result to all possible partitioning techniques is also given. For rectangular queries, we show that hexagonal partitioning has overall better I/O performance for a general class of range queries, except for rectilinear queries, in which case rectangular grid partitioning is superior. By using current algorithms for rectangular grid partitioning, parallel storage and retrieval algorithms for hexagonal partitioning can be constructed. Some of these results carry over to circular partitioning of the data—which is an example of a non-convex region.     

JADLib-科学计算数据高层I/O软件库

JADLib是为满足大规模复杂结构数据的存储与共享需求而研制的科学数据I/O软件库。其目标是设计并实现管理科学计算网格数据的数据存储模型,支持多种复杂结构数据的表示与操作,应用程序接口直观、易掌握,文件格式统一、可直接可视化,提供并行I/O、数居子集访问、压缩存储等高性能存储机制,支持多类科学计算程序跨平台使用,目前已应用到惯性约束聚变、高功率微波、计算流体力学、材料科学等多个研究领域中。实际应用表明,JADLib对于解决数值模拟软件数据存储及后处理分析所面临的I/O效率与组织管理问题具有很好的应用效果。     

数据描述机制研究及在地质行业软件中的应用

大型的地质行业软件系统使用到多达几十种数据类型。在进行数据输入输出的时候,绝大多数数据的处理流程基本是一致的,但如果不能实现数据的统一描述,就无法实现该处理功能模块的复用,使得实现和维护成本很高。通过对十几种常用石油地质数据的组成和内部结构进行的研究,本文分析并提出了一套数据描述机制,论述了其实现的一些关键原理,并在地质行业软件数据输入输出系统得到验证。     

云存储上的I/O特征获取机制

为有效地获取云存储系统上的I/O特征,从云存储的体系结构出发,根据不同层面的结构特征提出一种层次化的I/O特征获取机制。该机制从全局云平台、集群和局部物理节点两个方面收集和分析云存储系统上的I/O特征数据,通过在云存储虚拟层嵌入监听模块来采集I/O特征,并通过统计分析模块对收集的数据做在线的分析。实验结果表明,该机制能够有效获取云存储系统的I/O特征,为云存储系统性能优化提供参考。     

数据描述机制研究及在地质行业软件中的应用

大型的地质行业软件系统使用到多这几十种数据类型。在进行数据输入输出的时候，绝大多数数据的处理流程基本是一致的，但如果不能实现数据的统一描述，就无法实现该处理功能模块的复用，使得实现和维护成本很高。通过对十几种常用石油地质数据的组成和内部结构进行的研究，本文分析并提出了一套数据描述机制，论述了其实现的一些关键原理，并在地质行业软件数据输入输出系统得到验证。     

Matlab的数据文件I/O的实现方法

在实现Matlab和其它应用程序的数据共享时，Matlab常需要读写数据文件。本文详细讨论了Matlab数据文件I／O的实现方法，并给出了程序实例。     

Maintaining I/O Data Coherence in Embedded Multicore Systems

In embedded systems, multiple cores mean multiple caches and often multiple cache levels. Consequently, maintaining coherency between the cores' caches and the data generated or consumed by I/O devices is challenging, with different solutions trading off hardware versus software complexity. The optimal approach for I/O data coherence depends on application and system characteristics, and might require a combination of techniques.     

I/O Acceleration via Multi-Tiered Data Buffering and Prefetching

Modern High-Performance Computing(HPC)systems are adding extra layers to the memory and storage hierarchy,named deep memory and storage hierarchy(DMSH),to increase I/O performance.New hardware technologies,such as NVMe and SSD,have been introduced in burst buffer installations to reduce the pressure for external storage and boost the burstiness of modern I/O systems.The DMSH has demonstrated its strength and potential in practice.However,each layer of DMSH is an independent heterogeneous system and data movement among more layers is significantly more complex even without considering heterogeneity.How to efficiently utilize the DMSH is a subject of research facing the HPC community.Further,accessing data with a high-throughput and low-latency is more imperative than ever.Data prefetching is a well-known technique for hiding read latency by requesting data before it is needed to move it from a high-latency medium(e.g.,disk)to a low-latency one(e.g.,main memory).However,existing solutions do not consider the new deep memory and storage hierarchy and also suffer from under-utilization of prefetching resources and unnecessary evictions.Additionally,existing approaches implement a client-pull model where understanding the application's I/O behavior drives prefetching decisions.Moving towards exascale,where machines run multiple applications concurrently by accessing files in a workflow,a more data-centric approach resolves challenges such as cache pollution and redundancy.In this paper,we present the design and implementation of Hermes:a new,heterogeneous-aware,multi-tiered,dynamic,and distributed I/O buffering system.Hermes enables,manages,supervises,and,in some sense,extends I/O buffering to fully integrate into the DMSH.We introduce three novel data placement policies to efficiently utilize all layers and we present three novel techniques to perform memory,metadata,and communication management in hierarchical buffering systems.Additionally,we demonstrate the benefits of a truly hierarchical data prefetcher that adopts a server-push approach to data prefetching.Our evaluation shows that,in addition to automatic data movement through the hierarchy,Hermes can significantly accelerate I/O and outperforms by more than 2x state-of-the-art buffering platforms.Lastly,results show 10%-35%performance gains over existing prefetchers and over 50%when compared to systems with no prefetching.     

工业控制应用程序的两种设计方法

本介绍了常用的两种工业控制系统应用程序的设计方法,中以研华工业控制计算机作为例子,分别讨论在ＤＯＳ与Ｗｉｎｄｏｗｓ两种环境下数据采集和控制程序的设计,并对二的优缺点尤其是可行性进行了比较。     

高速自动校直切断机的实时多任务程序设计

本介绍了ＰＣＣ（Ｐｒｏｇｒａｍｍｉｎｇ Ｃｏｍｐｕｔｅｒ Ｃｏｎｔｒｏｌｌｅｒ）的多任务及多任务程序设计在高速自动校直切断机上的实现。给出了软件结构框图、任务级别的划分原则。     

Multi-bank闪存文件系统的一种I/O调度机制

闪存以其体积小、抗震性强、能耗低、读取速度快等特点,被广泛应用于存储系统中。NOOP是闪存上传统的调度方法,但是NOOP的I/O性能较低,不能满足很多应用程序的要求。根据闪存读取速度快、多个banks(chips)可以并行运行等特点,提出了一种基于闪存文件系统YAFFS的Multi-bank闪存调度方法(简称MBS)。MBS并行地执行请求,且给予读请求更高的优先级。MBS根据AVL-based-tree机制识别出的写请求属性动态地将其分配到合适的bank中。实验结果表明,相比NOOP,MBS调度具有更高的I/O吞吐率、更短的请求响应时间并具有均匀的bank擦除次数和利用率。