When key-value (KV) stores use SSDs for storing a large number of items, oftentimes they also require large in-memory data structures including indices and caches to be traversed to reduce IOs. This paper considers offloading most of such data structures from the costly host DRAM to secondary memory whose latency is in the microsecond range, an order of magnitude longer than those of DIMM-mounted persistent memory and currently available CXL memory devices. While emerging microsecond-latency memory, such as one based on flash memory, is likely to cost much less than DRAM, it can significantly slow down pointer-chasing on those in-memory data structures of SSD-based KV stores if naively employed, although its impact has not been well studied. This paper analyzes and evaluates the impact of microsecond-level memory latency on the throughput of SSD-based KV operations. Our analysis finds that a well-known latency-hiding technique of software prefetching for long-latency memory from user-level threads is effective for SSD-based KV stores. The novelty of our analysis lies in modeling how the interplay between prefetching and IO affects performance, from which we derive an equation that well explains the throughput degradation due to long memory latency. The model tells us that the presence of IO in KV operations significantly enhances their tolerance to memory latency, and the throughput degradation is expected to be small even if the memory latency extends to a few microseconds, leading to a finding that SSD-based KV stores can be made latency-tolerant without devising new techniques for microsecond-latency memory. To confirm this through experiments, we design a microbenchmark as well as modify existing SSD-based KV stores so that they issue prefetches for long-latency memory from user-level threads, and run them while placing most of in-memory data structures on FPGA-based memory with adjustable microsecond latency. The results demonstrate that their KV operation throughputs for varying memory latency can be well explained by our model, and the modified KV stores achieve near-DRAM throughputs for up to a memory latency of around 5 microseconds. This suggests the possibility that SSD-based KV stores involving latency-sensitive in-memory data traversal can use microsecond-latency memory as a cost-effective alternative to the host DRAM.

Locality sensitive hashing (LSH) is one of the widely-used approaches to approximate nearest neighbor search (ANNS) in high-dimensional spaces. The first work on LSH for the Euclidean distance, E2LSH, showed how ANNS can be solved efficiently at a sublinear query time in the database size with theoretically-guaranteed accuracy, although it required a large hash index size. Since then, several LSH variants having much smaller index sizes have been proposed. Their query time is linear or superlinear, but they have been shown to run effectively faster because they require fewer I/Os when the index is stored on hard disk drives and because they also permit in-memory execution with modern DRAM capacity. In this paper, we show that E2LSH is regaining the advantage in query speed with the advent of modern flash storage devices such as solid-state drives (SSDs). We evaluate E2LSH on a modern single-node computing environment and analyze its computational cost and I/O cost, from which we derive storage performance requirements for its external memory execution. Our analysis indicates that E2LSH on a single consumer-grade SSD can run faster than the state-of-the-art small-index methods executed in-memory. It also indicates that E2LSH with emerging high-performance storage devices and interfaces can approach in-memory E2LSH speeds. We implement a simple adaptation of E2LSH to external memory, E2LSH-on-Storage (E2LSHoS), and evaluate it for practical large datasets of up to one billion objects using different combinations of modern storage devices and interfaces. We demonstrate that our E2LSHoS implementation runs much faster than small-index methods and can approach in-memory E2LSH speeds, and also that its query time scales sublinearly with the database size beyond the index size limit of in-memory E2LSH.

For applications in which small-sized random accesses frequently occur for datasets that exceed DRAM capacity, placing the datasets on SSD can result in poor application performance. For the read-intensive case we focus on in this paper, low latency flash memory with microsecond read latency is a promising solution. However, when they are used in large numbers to achieve high IOPS (Input/Output operations Per Second), the CPU processing involved in IO requests is an overhead. To tackle the problem, we propose a new access method combining two approaches: 1) optimizing issuance and completion of the IO requests to reduce the CPU overhead. 2) utilizing many contexts with lightweight context switches by stackless coroutines. These reduce the CPU overhead per request to less than 10 ns, enabling read access with DRAM-like overhead, while the access latency longer than DRAM can be hidden by the context switches. We apply the proposed method to graph algorithms such as BFS (Breadth First Search), which involves many small-sized random read accesses. In our evaluation, the large graph data is placed on microsecond-latency flash memories within prototype boards, and it is accessed by the proposed method. As a result, for the synthetic and real-world graphs, the execution times of the graph algorithms are 88--141% of those when all the data are placed in DRAM.

We present a camera with switchable primaries using shiftable layers of color filter arrays (CFAs). By layering a pair of CMY CFAs in this novel manner we can switch between multiple sets of color primaries (namely RGB, CMY and RGBCY) in the same camera. In contrast to fixed color primaries (e.g. RGB or CMY), which cannot provide optimal image quality for all scene conditions, our camera with switchable primaries provides optimal color fidelity and signal to noise ratio for multiple scene conditions. Next, we show that the same concept can be used to layer two RGB CFAs to design a camera with switchable low dynamic range (LDR) and high dynamic range (HDR) modes. Further, we show that such layering can be generalized as a constrained satisfaction problem (CSP) allowing to constrain a large number of parameters (e.g. different operational modes, amount and direction of the shifts, placement of the primaries in the CFA) to provide an optimal solution. We investigate practical design options for shiftable layering of the CFAs. We demonstrate these by building prototype cameras for both switchable primaries and switchable LDR/HDR modes. To the best of our knowledge, we present, for the first time, the concept of shiftable layers of CFAs that provides a new degree of freedom in photography where multiple operational modes are available to the user in a single camera for optimizing the picture quality based on the nature of the scene geometry, color and illumination.

This paper presents a new automatic scheme for tracking a 3D non-rigid object surface such as a human face in a real-time video sequence. We introduce a coordinate-oriented error minimization method for estimating the tracking parameters, whereas we base our algorithm on a morphable 3D model consisting of a combination of 3D linear bases, and show that it is extremely well suited to the task of fitting the 3D model to the target object in real time. The algorithm is straightforward, allowing the parameters of an object's pose and non-rigid motion to be computed in an integrated manner. Also, it is found that the illumination variability on the object surface, for instance due to the target motion, can be handled easily. Through the experiments we not only show that on-line tracking is indeed possible, but also demonstrate the effect of our technique of video mimicking.

Abstract In this paper we describe a method for modeling and rendering dynamic behavior of fluids withsplashes and foam. A particle system is built into a fluid simulation system to represent an ocean wavecresting and spraying over another object. We use the Cubic Interpolated Propagation (CIP) method asthe fluid solver. The CIP method can solve liquid and gas together in the framework of fluid dynamicsand has high accuracy in the case of relatively coarse grids. This enables us to simulate the fluids in ashort time and describe the motion of splashes in the air that is associated with the liquid motion well.The foam floating on the water also can be described using the particle system. We integrate the rigidbody simulation with the fluid and particle system to create sophisticated scenes including splashes andfoam. We construct state change rules that are used with the particle system. This controls the generation,vanishing and transition rule of splashes and foam. The transition rule makes the seamless connection betweena splash and foam. We employed a fast volume rendering method with scattering effect for particles.One of the important features of our method is the combination of fast simulation and rendering techniques,which provides dynamic and realistic scenes in a short time.

Movies with actions and light effects of fluid objects are aesthetically pleasing and interesting. Until now, the calculation costs of simulation and rendering of fluid objects have been very high. Using a modern PC system and appropriate methods, we achieved a time of 10-20 seconds per frame for this application. Our system uses a full Navier-Stokes equation solver with uniform Eulerian mesh, marching cube isosurface techniques, Catmull-Clark subdivision surface techniques, ray tracing techniques on each vertex and conventional polygon base rendering by HW accelerator. In this paper, we describe the components of our system and the reasons for choosing them. By measuring CPU times of each process for some movie scenes of fluid objects, we evaluate this system. We consider what factors are important for creating movies of fluid objects with short TAT.