Data mining is beginning to be widely used in various application fields. Density based clustering algorithms perform data mining by grouping high-density regions of points to form clusters. In recent years, the data sizes and the problem complexity of this algorithm have increased significantly leading to slower execution of the applications. Faster engines that perform the application tasks quickly and efficiently are the need of the hour. In this paper, we propose a hardware accelerator for density based clustering applications. This accelerator improves the execution speed of the core kernels of this application, which include density calculation and the migration of points to denser regions. We show that this accelerator when integrated with general purpose processors, speed up the kernel execution times by at least 300X.

MEMS-based storage systems have recently generated significant interest due to their potential to be faster and more efficient than disks, while providing the non-volatility property. Designing data layouts for these devices is a challenging, important and interesting problem. In this paper, we explore various ways of placing a database on a MEMS-based storage architecture. Three novel data layouts are proposed after considering the MEMS device characteristics and the access patterns arising from queries. We then design the access methodology for each layout and evaluate these layouts based on their respective I/O service times. Overall, our results were able to identify the intricacies of placing data on a MEMS-based storage and also ascertain the large potential of MEMS-based devices for databases.

The tremendous growth of system memories has increased the capacities and capabilities of memory-resident embedded databases, yet current embedded databases need to be tuned in order to take advantage of new memory technologies. In this paper, we study the implications of hosting memory resident databases, and propose hardware and software (query-driven) techniques to improve their performance and energy consumption. We exploit the structured organization of memories, which enables a selective mode of operation in which banks are accessed selectively. Unused banks are placed in a lower power mode based on access pattern information. We propose hardware techniques that dynamically control the memory by making the system adapt to the access patterns that arise from queries. We also propose a software (query-directed) scheme that directly modifies the queries to reduce the energy consumption by ensuring uniform bank accesses. Our results show that these optimizations could lead to at the least 40% reduction in memory energy. We also show that query-directed schemes better utilize the low-power modes, achieving up to 68% improvement.

With the tremendous growth of system memories, memory-resident databases are increasingly becoming important in various domains. Newer memories provide a structured way of storing data in multiple chips, with each chip having a bank of memory modules. Current memory-resident databases are yet to take full advantage of the banked storage system, which offers a lot of room for performance and energy optimizations. In this paper, we identify the implications of a banked memory environment in supporting memory-resident databases, and propose hardware (memory-directed) and software (query-directed) schemes to reduce the energy consumption of queries executed on these databases. Our results show that high-level query-directed schemes (hosted in the query optimizer) better utilize the low-power modes in reducing the energy consumption than the respective hardware schemes (hosted in the memory controller), due to their complete knowledge of query access patterns. We extend this further and propose a query restructuring scheme and a multi-query optimization. Queries are restructured and regrouped based on their table access patterns to maximize the likelihood that data accesses are clustered. This helps increase the inter-access idle times of memory modules, which in turn enables a more effective control of their energy behavior. This heuristic is eventually integrated with our hardware optimizations to achieve maximum savings. Our experimental results show that the memory energy reduces by 90% if query restructuring method is applied along with basic energy optimizations over the unoptimized version. The system-wide performance impact of each scheme is also studied simultaneously.

Structured embedded databases are currently becoming an integrated part of embedded systems, thus, enabling higher standards in system automation. These embedded databases are typically memory resident. In this paper, we present a data-centric approach called data windowing that optimizes multiple queries issued to an embedded database. Traditional approaches improve the performance by optimizing the control flow of operations, whereas we target performance improvements based on the data that is brought into the system.

In recent years, both performance and power have become key factors in efficient memory design. In this paper, we propose a systematic approach to reduce the energy consumption of the entire memory hierarchy. We first evaluate an existing power-aware memory system where memory modules can exist in different power modes, and then propose on-chip memory module buffers, called Energy-Saver Buffers (ESB), which reside in-between the L2 cache and main memory. ESBs reduce the additional overhead incurred due to frequent resynchronization of the memory modules in a low-power state. An additional improvement is attained by using a model that dynamically resizes the active cache based on the varying needs of a program. Our experimental results demonstrate that an integrated approach can reduce the energy-delay product by as much as 50% when compared to a traditional non power-aware memory hierarchy.

Power consumption is becoming increasingly important for both embedded and high-performance systems. Off-chip data buses can be a major power consumer. In this paper we present a strategy called "power protocol" that tries to reduce the dynamic power dissipation on off-chip data buses. To accomplish this, our strategy reduces the number of bus lines that need to be activated for data transfer by employing a small cache (called "value cache") at each side of the off-chip data bus. These value caches keep track of the data values that have recently been transmitted over the bus. The entries in these caches are constructed in such a way that the contents of both the value caches are the same all the time. When a data value needs to be transmitted over the bus, we first check whether it is in the value cache of the sender. If it is, we transmit only the index of the data (i.e., its value cache address) instead of the actual data value and, the other side (receiver) can determine the data value by using this index and its value cache. Our experimental results using a set of fifteen benchmark codes from embedded systems domain show that power protocol is very effective in practice, and reduces the bit switching activity on the data bus by as much as 70.7% (with a value cache of 128 entries). We also present results from an implementation that combines our strategy with 1-to-2 encoding, a popular bus encoding strategy for low power. Our results indicate that this combined optimization strategy reduces bit switching activity by 67.8% on the average (across all benchmarks). These reductions in bit switching activity lead to more than 7% reduction on overall system energy on the average for a value cache of 256 entries. We also study the sensitivity of our savings to the value cache capacity and data cache capacity.