Building and using a scalable display wall system

Princeton's scalable display wall project explores building and using a large-format display with commodity components. The prototype system has been operational since March 1998. Our goal is to construct a collaborative space that fully exploits a large-format display system with immersive sound and natural user interfaces. Our prototype system is built with low-cost commodity components: a cluster of PCs, PC graphics accelerators, consumer video and sound equipment, and portable presentation projectors. This approach has the advantages of low cost and of tracking technology well, as high-volume commodity components typically have better price-performance ratios and improve at faster rates than special-purpose hardware. We report our early experiences in building and using the display wall system. In particular, we describe our approach to research challenges in several specific research areas, including seamless tiling, parallel rendering, parallel data visualization, parallel MPEG decoding, layered multiresolution video input, multichannel immersive sound, user interfaces, application tools, and content creation     

改进的多投影仪显示墙几何校正技术

针对传统几何校正的不足,提出一种改进的几何校正的方法,只需少许人工干预就能很高精度的完成几何校正.介绍一种相机自动定位和拍照的方法,避免人工调整相机位置的繁琐工作,实现相机控制的自动化;提出一种基于递归的去除图片公共噪声区域算法,更精确地识别出特征点;通过临近的特征点,使用平行四边形插值算法与最小二乘法曲线拟合算法对被遮挡住的特征点坐标进行估计.实验结果表明,相机控制方法提高了几何校正的自动化程度,去噪算法提高了识别特征点的精度,平行四边形插值算法可以很好地对被遮挡的特征点坐标进行估计.     

A scalable distributed paradigm for multi-user interaction with tiled rear projection display walls

We present the first distributed paradigm for multiple users to interact simultaneously with large tiled rear projection display walls. Unlike earlier works, our paradigm allows easy scalability across different applications, interaction modalities, displays and users. The novelty of the design lies in its distributed nature allowing well-compartmented, application independent, and application specific modules. This enables adapting to different 2D applications and interaction modalities easily by changing a few application specific modules. We demonstrate four challenging 2D applications on a nine projector display to demonstrate the application scalability of our method: map visualization, virtual graffiti, virtual bulletin board and an emergency management system. We demonstrate the scalability of our method to multiple interaction modalities by showing both gesture-based and laser-based user interfaces. Finally, we improve earlier distributed methods to register multiple projectors. Previous works need multiple patterns to identify the neighbors, the configuration of the display and the registration across multiple projectors in logarithmic time with respect to the number of projectors in the display. We propose a new approach that achieves this using a single pattern based on specially augmented QR codes in constant time. Further, previous distributed registration algorithms are prone to large misregistrations. We propose a novel radially cascading geometric registration technique that yields significantly better accuracy. Thus, our improvements allow a significantly more efficient and accurate technique for distributed self-registration of multi-projector display walls.     

Tele-immersive environment with tiled display wall for intuitive remote collaborative work

In remote collaborative work via WAN, sharing and recognizing various high-quality visual contents such as photography, visualization image, and real video streaming is extremely important. Supporting a high-quality display of these contents on a large-scale display system is necessary to support intellectual remote collaborative work. However, these contents are currently magnified in low resolution on a general projector used as large-sized display equipment, and these equipments are difficult to display the contents with sufficient quality. In this paper, we have focused on the tiled display wall technology which configure a wide-area screen with two or more LCD and tried to display realistic high-resolution visual contents to solve these issues. We have constructed a tele-immersive environment with a tiled display wall, and have studied the availability for intuitive remote collaborative work by implementing various collaborative applications for the effective display of high-resolution contents as well as developing interaction techniques for enormous visual contents in this environment. As a result, we have showed that the practical use of a tiled display wall is useful in the construction of intellectual remote collaborative environment.     

Analyzing Google Earth application in a heterogeneous commodity cluster display wall

Nowadays, clusters of interconnected workstations have become a common solution for powering large composite displays, or “cluster display walls”, to visualize high resolution images. Our paper is focused on analyzing a specific cluster display wall developed by Google, named Liquid Galaxy, made up of heterogeneous commodity hardware with different degrees of heterogeneity, running master-slave (Google Earth) and client-server (Quake III Arena) multimedia applications. With this in mind, we define and test different scenarios, representing the behavior of many kinds of users. Our results show that the CPU, memory and network are good enough to execute the client-server application, while, depending on the user behavior, the external network constitutes the bottleneck of the system in Google Earth. So, the master-slave application has focused our attention. Likewise, in order to analyze the users’ point of view when interacting with Google Earth in the Liquid Galaxy, we define a new metric, named Visualization Rate (VR), which enables a relationship to be established between the user experience and the platform performance. In order to set the minimum acceptable value of the VR parameter according to users perception, we carried out different tests with real users. Then, this minimum threshold was compared with the VR value obtained from the automated benchmarking performed afterwards on clusters with different heterogeneity degrees. Finally, we analyzed the VR trend when the Liquid Galaxy is scaled from 3 up to 8 nodes in both the homogeneous and heterogeneous architectures to study the scalability of the system.     

Cost-effective haptic-based networked virtual environments with high-resolution tiled display

In this paper, a haptic-based NVE (networked virtual environment) supporting high-resolution tiled display is proposed with a resource management scheme for future home applications such as a haptic-based networked game. Although NVEs with haptic interaction and immersive display have been developed in previous studies, they usually require expensive system configurations. In order to implement a cost-effective system, our proposed design includes a tiled display supporting high-resolution with several low-cost LCDs. The display nodes of the tiled display also have low processing and storage resource requirements because they only need to handle display-ready pixels received from the application node. The proposed resource management scheme, called as an object-based display scheme, reduces the resource requirements of the application node that would otherwise require significant resources to manage all the display nodes and to provide a user with haptic feedback. The proposed scheme segments graphic scenes into several pixelated virtual objects and assigns different frame rates to each object according to the interest of user. Experimental results confirm that the proposed scheme reduces the required network bandwidth and appropriately assigns the limited processing resources to graphic and haptic renderings for a high-level visual and haptic quality.     

Evaluation study on realistic sensation in tele-communication environment with ultra-resolution video by multiple cameras on tiled display wall

To enhance a high-realistic sensation for participants in tele-communication over the Internet, space sharing by displaying super-quality video is effective. However, in commonly used tele-communication systems, participants have found it difficult to feel an ordinary presence and realistic sensation in real environments, and an effective solution has still not been proposed. We have constructed a tele-communication environment to display an ultra-resolution video which realizes a display resolution over 4K on a tiled display wall by multi-transmitting each video captured by multiple cameras. Nonetheless, the need for objective evaluation and analysis on the realistic sensation that participants feel in tele-communication has been increasing. However, there are only a few case studies on detailed analysis and evaluation of the factors required for realistic sensation in tele-communication. In this paper, we have conducted an experiment to evaluate and analyze the effectiveness of realistic sensation and its effect on participants in this tele-communication environment. From experimental results, we have shown that this tele-communication environment has a strong tendency to provide higher realistic sensation for estimators.     

GraphMap: scalable iterative graph processing using NoSQL

The Journal of Supercomputing - Despite having several distributed graph processing frameworks, scalable iterative processing of large graphs is a challenging problem since the graph and...     

基于分块地形的混合数据结构三维公路建模

为了权衡三维公路建模中数据高精度性以及渲染高效性的矛盾,在地形分块基础上提出了一种在场景中规则网格与不规则三角网并存的混合数据结构三维公路建模方法。此方法结合规则网格与不规则三角网两种地形表示方式的优缺点,若地形子块有公路覆盖,则利用Delaunay三角网方法精细绘制,否则基于规则网格LOD(细节层次)绘制,以此来提高渲染效率。针对此混合结构产生的块间裂缝问题,提出了对低细节层次节点增点的修补方案,以及针对此方法的特点提出了基于有向线段与增量步长的地形镂空算法,实现了地形与公路的无缝融合。实验结果表明,该方案可有效适用于三维公路设计。     

MiniCon: A scalable algorithm for answering queries using views

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously materialized views over the database, rather than accessing the database relations. The problem has received significant attention because of its relevance to a wide variety of data management problems, such as data integration, query optimization, and the maintenance of physical data independence. To date, the performance of proposed algorithms has received very little attention, and in particular, their scale up in the presence of a large number of views is unknown. We first analyze two previous algorithms, the bucket algorithm and the inverse-rules, and show their deficiencies. We then describe the MiniCon, a novel algorithm for finding the maximally-contained rewriting of a conjunctive query using a set of conjunctive views. We present the first experimental study of algorithms for answering queries using views. The study shows that the MiniCon scales up well and significantly outperforms the previous algorithms. We describe an extension of the MiniCon to handle comparison predicates, and show its performance experimentally. Finally, we describe how the MiniCon can be extended to the context of query optimization. Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 28 June 2001     

StreamTMC: Stream compilation for tiled multi-core architectures

Tiled multi-core architectures have become an important kind of multi-core design for its good scalability and low power consumption. Stream programming has been productively applied to a number of important application domains. It provides an attractive way to exploit the parallelism. However, the architecture characteristics of large amounts of cores, memory hierarchy and exposed communication between tiles have presented a performance challenge for stream programs running on tiled multi-cores. In this paper, we present StreamTMC, an efficient stream compilation framework that optimizes the execution of stream applications for the tiled multi-core. This framework is composed of three optimization phases. First, a software pipelining schedule is constructed to exploit the parallelism. Second, an efficient hybrid of SPM and cache buffer allocation algorithm and data copy elimination mechanism is proposed to improve the efficiency of the data access. Last, a communication aware mapping is proposed to reduce the network communication and synchronization overhead. We implement the StreamTMC compiler on Godson-T, a 64-core tiled architecture and conduct an experimental study to verify the effectiveness. The experimental results indicate that StreamTMC can achieve an average of 58% improvement over the performance before optimization.     

MI-File: using inverted files for scalable approximate similarity search

We propose a new efficient and accurate technique for generic approximate similarity searching, based on the use of inverted files. We represent each object of a dataset by the ordering of a number of reference objects according to their distance from the object itself. In order to compare two objects in the dataset, we compare the two corresponding orderings of the reference objects. We show that this representation enables us to use inverted files to obtain very efficiently a very small set of good candidates for the query result. The candidate set is then reordered using the original similarity function to obtain the approximate similarity search result. The proposed technique performs several orders of magnitude better than exact similarity searches, still guaranteeing high accuracy. To also demonstrate the scalability of the proposed approach, tests were executed with various dataset sizes, ranging from 200,000 to 100 million objects.     

EvAg: a scalable peer-to-peer evolutionary algorithm

This paper studies the scalability of an Evolutionary Algorithm (EA) whose population is structured by means of a gossiping protocol and where the evolutionary operators act exclusively within the local neighborhoods. This makes the algorithm inherently suited for parallel execution in a peer-to-peer fashion which, in turn, offers great advantages when dealing with computationally expensive problems because distributed execution implies massive scalability. In this paper we show another advantage of this algorithm: We experimentally demonstrate that it scales up better than traditional alternatives even when executed in a sequential fashion. In particular, we analyze the behavior of several EAs on well-known deceptive trap functions with varying sizes and levels of deceptiveness. The results show that the new EA requires smaller optimal population sizes and fewer fitness evaluations to reach solutions. The relative advantage of the new EA is more outstanding as problem hardness and size increase. In some cases the new algorithm reduces the computational efforts of the traditional EAs by several orders of magnitude.     

Paradigm: a highly scalable shared-memory multicomputerarchitecture

Paradigm (parallel distributed global memory), a shared-memory multicomputer architecture that is being developed to show that one can build a large-scale machine using high-performance microprocessors, is discussed. The Paradigm architecture allows a parallel application program to execute any of its tasks on any processor in the machine, with all the tasks in a single address space. The focus is on novel design techniques that support scalability. The key performance issues are identified, and some results to date from this work and experience with the VMP architecture design on which it is based are summarized     

Qmol: a program for molecular visualization on Windows-based PCs

With the advent of powerful, inexpensive graphics hardware, a variety of molecular modelling tools are now available for personal computers (PCs). While a host of high-quality, free visualization programs exist for Unix-like operating systems, there are relatively few available for Microsoft Windows. Most programs that do run under Windows are designed to interactively visualize experimental data and cannot read binary trajectory data generated by molecular simulations. In addition, many of these programs do not accept command line arguments, limiting their ability to serve as a “helper” application to be run by other applications. To fill this gap in functionality, we present Qmol—a program designed for viewing the output of simulations and theoretical calculations of peptides and small molecules.     

High-performance optimizations on tiled many-core embedded systems: a matrix multiplication case study

Technological advancements in the silicon industry, as predicted by Moore’s law, have resulted in an increasing number of processor cores on a single chip, giving rise to multicore, and subsequently many-core architectures. This work focuses on identifying key architecture and software optimizations to attain high performance from tiled many-core architectures (TMAs)—an architectural innovation in the multicore technology. Although embedded systems design is traditionally power-centric, there has been a recent shift toward high-performance embedded computing due to the proliferation of compute-intensive embedded applications. The TMAs are suitable for these embedded applications due to low-power design features in many of these TMAs. We discuss the performance optimizations on a single tile (processor core) as well as parallel performance optimizations, such as application decomposition, cache locality, tile locality, memory balancing, and horizontal communication for TMAs. We elaborate compiler-based optimizations that are applicable to TMAs, such as function inlining, loop unrolling, and feedback-based optimizations. We present a case study with optimized dense matrix multiplication algorithms for Tilera’s TILEPro64 to experimentally demonstrate the performance and performance per watt optimizations on TMAs. Our results quantify the effectiveness of algorithmic choices, cache blocking, compiler optimizations, and horizontal communication in attaining high performance and performance per watt on TMAs.     

A scalable algorithm for mining maximal frequent sequences using a sample

In this paper, we propose an efficient scalable algorithm for mining Maximal Sequential Patterns using Sampling (MSPS). The MSPS algorithm reduces much more search space than other algorithms because both the subsequence infrequency-based pruning and the supersequence frequency-based pruning are applied. In MSPS, a sampling technique is used to identify long frequent sequences earlier, instead of enumerating all their subsequences. We propose how to adjust the user-specified minimum support level for mining a sample of the database to achieve better overall performance. This method makes sampling more efficient when the minimum support is small. A signature-based method and a hash-based method are developed for the subsequence infrequency-based pruning when the seed set of frequent sequences for the candidate generation is too big to be loaded into memory. A prefix tree structure is developed to count the candidate sequences of different sizes during the database scanning, and it also facilitates the customer sequence trimming. Our experiments showed MSPS has very good performance and better scalability than other algorithms. Congnan Luo received the B.E. degree in Computer Science from Tsinghua University, Beijing, P.R. China, in 1997, the M.S. degree in Computer Science from the Institute of Software, Chinese Academy of Sciences, Beijing, P.R. China, in 2000, and the Ph.D. degree in Computer Science and Engineering from Wright State University, Dayton, OH, in 2006. Currently he is a technical staff at the Teradata division of NCR in San Diego, CA, and his research interests include data mining, machine learning, and databases. Soon M. Chung received the B.S. degree in Electronic Engineering from Seoul National University, Korea, in 1979, the M.S. degree in Electrical Engineering from Korea Advanced Institute of Science and Technology, Korea, in 1981, and the Ph.D. degree in Computer Engineering from Syracuse University, Syracuse, New York, in 1990. He is currently a Professor in the Department of Computer Science and Engineering at Wright State University, Dayton, OH. His research interests include database, data mining, Grid computing, text mining, XML, and parallel and distributed processing.