Main Memory-Based Algorithms for Efficient Parallel Aggregation for Temporal Databases

The ability to model the temporal dimension is essential to many applications. Furthermore, the rate of increase in database size and stringency of response time requirements has out-paced advancements in processor and mass storage technology, leading to the need for parallel temporal database management systems. In this paper, we introduce a variety of parallel temporal aggregation algorithms for the shared-nothing architecture; these algorithms are based on the sequential Aggregation Tree algorithm. We are particularly interested in developing parallel algorithms that can maximally exploit available memory to quickly compute large-scale temporal aggregates without intermediate disk writes and reads. Via an empirical study, we found that the number of processing nodes, the partitioning of the data, the placement of results, and the degree of data reduction effected by the aggregation impacted the performance of the algorithms. For distributed result placement, we discovered that Greedy Time Division Merge was the obvious choice. For centralized results and high data reduction, Pairwise Merge was preferred for a large number of processing nodes; for low data reduction, it only performed well up to 32 nodes. This led us to a centralized variant of Greedy Time Division Merge which was best for the remaining cases. We present a cost model that closely predicts the running time of Greedy Time Division Merge.     

Negative Offset Operation of Four-Transistor CMOS Image Pixels for Increased Well Capacity and Suppressed Dark Current

This letter presents an electrical method to reduce dark current as well as increase well capacity of four-transistor pixels in a CMOS image sensor, utilizing a small negative offset voltage to the gate of the transfer (TX) transistor particularly only when the TX transistor is off. As a result, using a commercial pixel in a 0.18 mum CMOS process, the voltage drop due to dark current of the pinned photodiode (PPD) is reduced by 6.1 dB and the well capacity is enhanced by 4.4 dB, which is attributed to the accumulated holes and the increased potential barrier near the PPD, respectively.     

Ultra-thin and isolated dots in polycrystalline lead zirconate titanate films

Size effects with critical thickness or minimum volume for ferroelectricity are of importance in the application of polycrystalline PZT thin films as future memory devices and as storage media. Isolated dots of perovskite phases in the matrix of pyrochlore were synthesized by isothermal annealing through transformation from amorphous to perovskite. Control of the transformation kinetics allows us to produce the isolated ferroelectric dots with a diameter of 50 nm. Domain structure of the isolated dots is also studied by piezoresponse force microscopy. As prepared, all isolated dots contain perpendicularly polarized monodomains. Domain structures and switching behaviors of the isolated dots are similar to those of the single crystalline PZT films. Polycrystalline PZT films with a thickness of 50 nm were also investigated. They show excellent piezoresponse properties and switching behaviors. Ultra-thin polycrystalline PZT films can play a major role in the application of future ferroelectric memories and field-effect transistors as well as for storage media using the local probe technique.     

Locating XML Documents in a Peer-to-Peer Network Using Distributed Hash Tables

One of the key challenges in a peer-to-peer (P2P) network is to efficiently locate relevant data sources across a large number of participating peers. With the increasing popularity of the extensible markup language (XML) as a standard for information interchange on the Internet, XML is commonly used as an underlying data model for P2P applications to deal with the heterogeneity of data and enhance the expressiveness of queries. In this paper, we address the problem of efficiently locating relevant XML documents in a P2P network, where a user poses queries in a language such as XPath. We have developed a new system called psiX that runs on top of an existing distributed hashing framework. Under the psiX system, each XML document is mapped into an algebraic signature that captures the structural summary of the document. An XML query pattern is also mapped into a signature. The query's signature is used to locate relevant document signatures. Our signature scheme supports holistic processing of query patterns without breaking them into multiple path queries and processing them individually. The participating peers in the network collectively maintain a collection of distributed hierarchical indexes for the document signatures. Value indexes are built to handle numeric and textual values in XML documents. These indexes are used to process queries with value predicates. Our experimental study on PlanetLab demonstrates that psiX provides an efficient location service in a P2P network for a wide variety of XML documents.     

Runtime and language support for compiling adaptive irregular programs on distributed-memory machines

In many scientific applications, arrays containing data are indirectly indexed through indirection arrays. Such scientific applications are called irregular programs and are a distinct class of applications that require special techniques for parallelization. This paper presents a library called CHAOS, which helps users implement irregular programs on distributed-memory message-passing machines, such as the Paragon, Delta, CM-5 and SP-1. The CHAOS library provides efficient runtime primitives for distributing data and computation over processors; it supports efficient index translation mechanisms and provides users high-level mechanisms for optimizing communication. CHAOS subsumes the previous PARTI library and supports a larger class of applications. In particular, it provides efficient support for parallelization of adaptive irregular programs where indirection arrays are modified during the course of computation. To demonstrate the efficacy of CHAOS, two challenging real-life adaptive applications were parallelized using CHAOS primitives: a molecular dynamics code, CHARMM, and a particle-in-cell code, DSMC. Besides providing runtime support to users, CHAOS can also be used by compilers to automatically parallelize irregular applications. This paper demonstrates how CHAOS can be effectively used in such a framework. By embedding CHAOS primitives in the Syracuse Fortran 90D/HPF compiler, kernels taken from the CHARMM and DSMC codes have been automatically parallelized.     

Characterization of self-assembling isolated ferroelectric domains by scanning force microscopy

Lead zirconate titanate (PZT) thin films were prepared by a sol–gel process on platinized Si substrate. Their microstructure and surface morphology were characterized by XRD and Scanninn Force Microscopy. Phase transformation of the prepared PZT films from pyrochlore to ferroelectric was observed by XRD and PFM (piezoresponse force microscopy), respectively. Self-assembling nano-structured ferroelectric phases are fabricated by solution deposition technique followed by the controlling kinetics of the transformation. Complex structures of ferroelectric domains in the isolated ferroelectric phases were found in the furnace annealed PZT films in the temperature range of 400–500°C. Single ferroelectric domain structure in the isolated ferroelectric phases could be found in thinner PZT films and used to study the size effect of laterally confined ferroelectric domains.     

Strained‐SiGe Complementary MOSFETs Adopting Different Thicknesses of Silicon Cap Layers for Low Power and High Performance Applications

We introduce a strained‐SiGe technology adopting different thicknesses of Si cap layers towards low power and high performance CMOS applications. By simply adopting 3 and 7 nm thick Si‐cap layers in n‐channel and p‐channel MOSFETs, respectively, the transconductances and driving currents of both devices were enhanced by 7 to 37% and 6 to 72%. These improvements seemed responsible for the formation of a lightly doped retrograde high‐electron‐mobility Si surface channel in nMOSFETs and a compressively strained high‐hole‐mobility Si_0.8Ge_0.2 buried channel in pMOSFETs. In addition, the nMOSFET exhibited greatly reduced subthreshold swing values (that is, reduced standby power consumption), and the pMOSFET revealed greatly suppressed 1/f noise and gate‐leakage levels. Unlike the conventional strained‐Si CMOS employing a relatively thick (typically > 2 µm) Si_xGe_1‐x relaxed buffer layer, the strained‐SiGe CMOS with a very thin (20 nm) Si_0.8Ge_0.2 layer in this study showed a negligible self‐heating problem. Consequently, the proposed strained‐SiGe CMOS design structure should be a good candidate for low power and high performance digital/analog applications.     

Adaptive and incremental processing for distance join queries

A spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. Additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in online query processing or Internet search environments. These requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. In this paper, we first present an efficient k-distance join algorithm that uses spatial indexes such as R-trees. Bidirectional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. Furthermore, we propose adaptive multistage algorithms for k-distance join and incremental distance join operations. Our performance study shows that the proposed adaptive multistage algorithms outperform previous work by up to an order of magnitude for both k-distance, join and incremental distance join queries, under various operational conditions.