Perhaps the most influential result in the theory of caches is the following theorem due to Sleator and Tarjan: With O(1) resource augmentation, the basic LRU eviction policy is guaranteed to be O(1)-competitive with the optimal offline policy.

The TLB is increasingly a bottleneck for big data applications. In most designs, the number of TLB entries are highly constrained by latency requirements, and growing much more slowly than the working sets of applications. Many solutions to this problem, such as huge pages, perforated pages, or TLB coalescing, rely on physical contiguity for performance gains, yet the cost of defragmenting memory can easily nullify these gains. This paper introduces mosaic pages, which increase TLB reach by compressing multiple, discrete translations into one TLB entry. Mosaic leverages virtual contiguity for locality, but does not use physical contiguity. Mosaic relies on recent advances in hashing theory to constrain memory mappings, in order to realize this physical address compression without reducing memory utilization or increasing swapping. This paper presents a full-system prototype of Mosaic, in gem5 and modified Linux. In simulation and with comparable hardware to a traditional design, mosaic reduces TLB misses in several workloads by 6-81%. Our results show that Mosaic’s constraints on memory mappings do not harm performance, we never see conflicts before memory is 98% full in our experiments — at which point, a traditional design would also likely swap. Once memory is over-committed, Mosaic swaps fewer pages than Linux in most cases. Finally, we present timing and area analysis for a verilog implementation of the hashing function required on the critical path for the TLB, and show that on a commercial 28nm CMOS process; the circuit runs at a maximum frequency of 4 GHz, indicating that a mosaic TLB is unlikely to affect clock frequency.

Burst buffers tolerate I/O spikes in High-Performance Computing environments by using a non-volatile flash technology. Burst buffers are commonly located between parallel file systems and compute nodes, handling bursty I/Os in the middle. In this architecture, burst buffers are shared resources. The performance of an SSD is significantly reduced when it is used excessively because of garbage collection, and we have observed that SSDs in a burst buffer become slow when many users simultaneously use the burst buffer. To mitigate the performance problem, we propose a new user-level I/O isolation framework in a High-Performance Computing environment using a multi-streamed SSD. The multi-streamed SSD allocates the same flash block for I/Os in the same stream. We assign a different stream to each user; thus, the user can use the stream exclusively. To evaluate the performance, we have used open-source supercomputing workloads and I/O traces from real workloads in the Cori supercomputer at the National Energy Research Scientific Computing Center. Via user-level I/O isolation, we have obtained up to a 125% performance improvement in terms of I/O throughput. In addition, our approach reduces the write amplification in the SSDs, leading to improved SSD endurance. This user-level I/O isolation framework could be applied to deployed burst buffers without having to make any user interface changes.

Small touchscreen interfaces such as a smartwatch have usability problems due to the small screen. One solution to these problems is to utilize the space around the smartwatch as continuous input space for the touchscreen interface. We defined four steps for a gesture that starts on the touchscreen and continues in the air. The goal of this definition was to bring the experience of large touchscreen devices into a smartwatch usage. We compared design options for the four steps and made decisions for the options based on the results of four user experiments. We expect that gestures designed based on these decisions will be both easy to learn and robust.

A watch-back tactile display (WBTD) is expected to be a viable supplement to the user interface limitations of a smartwatch. However, its design requires that many design parameters such as tactor types and stimulus patterns be determined. We conducted a series of experiments to explore the design space of a WBTD consisting of 3×3 tactors. We demonstrated that tactor types and the temporal patterns and locus of a stimulus produce statistically significant effects on the efficiency of a WBTD. The experimental results can act as a practical guideline for the design of an efficient WBTD.

A page transition operation on touch interfaces is a common and frequent subtask when one conducts a drag-like operation such as selecting text and dragging an icon. Traditional page transition gestures such as scrolling and flicking gestures, however, cannot be conducted while conducting the drag-like operation since they have a confliction. We proposed Push-Push that is a new drag-like operation not in conflict with page transition operations. Thus, page transition operations could be conducted while performing Push-Push. To design Push-Push, we utilized the hover and pressed states as additional input states of touch interfaces. The results from two experiments showed that Push-Push has an advantage on increasing performance and qualitative opinions of users while reducing the subjective overload.

Although reliefs are frequently used to add patterns to product surfaces, there is a lack of interaction techniques to model reliefs on the surface of virtual objects. We adopted the repoussé and chasing artwork techniques in an alternative interaction technique to model relief on virtual surfaces. To support this interaction technique, we developed the double-sided touchpad Trampoline that can detect the position and force of a finger touch on both sides. Additionally, Trampoline provides users with elastic feedback, as its surface consists of a stretchable fabric. We implemented a relief application with this device and the developed interaction technique. An informal user study showed that the proposed system can be a promising solution to create reliefs.

In this paper, we explore the possibility of a long touchpad that utilizes the entire area below the keyboard of a laptop computer. An essential prerequisite for such a touchpad is a robust palm rejection method, which we satisfy using a proximity-sensing touchpad. We developed LongPad, a proximity-sensing optical touchpad that is as wide as a laptop keyboard, and implemented a palm rejection algorithm that utilizes proximity images from LongPad. In a user study conducted, we observed that LongPad rejected palm touches almost perfectly while participants were repeating typing and pointing tasks. We also summarize the new design space enabled by LongPad and demonstrate a few of the interaction techniques it facilitates.

Our goal is to show that it is possible to automatically infer social relationship types among people who stay together in an organization by analyzing communication patterns. We collected indoor co-location data and instant messenger data from 22 participants for one month. Based on the data, we designed and explored several indicators which are considered to be useful for mining social relationship types. We applied machine learning techniques using the indicators and found that it is possible to develop an intelligent method to infer social relationship types.

We explored the possibility of touch-screen-like interaction with a remote control in the TV-viewing environment. A shadow representing the user's thumb touches the screen, presses a button, flicks a cover-flow list, and draws a simple stroke, while the thumb stays and moves on and above the touchpad. In order to implement the concept we developed an optical touchpad for tracking the thumb hovering over its surface, and designed a TV application to demonstrate possible new interaction styles. Throughout two iterations of prototyping, we corrected some of our false expectations, and also verified its potential as a viable option for a TV remote control. This paper presents technical issues and requirements for the hover-tracking touchpad and a complete report of our user studies to explore touch-screen-like interaction for the TV.

Six-degrees-of-freedom (6-DOF) trackers, which were mainly for professional computer applications, are now in demand by everyday consumer applications. With the requirements of consumer electronics in mind, we designed an optical 6-DOF tracker where a few photo-sensors can track the position and orientation of an LED cluster. The operating principle of the tracker is basically source localization by solving an inverse problem. We implemented a prototype system for a TV viewing environment, verified the feasibility of the operating principle, and evaluated the basic performance of the prototype system in terms of accuracy and speed. We also examined its application possibility to different environments, such as a tabletop computer, a tablet computer, and a mobile spatial interaction environment.