In-memory key-value cache systems, such as Memcached and Redis, are essential in today's data centers. A key mission of such cache systems is to identify the most valuable data for caching. To achieve this, the current system design keeps track of each key-value item's access and attempts to make accurate estimation on its temporal locality. All it aims is to achieve the highest cache hit ratio. However, as cache capacity quickly increases, the overhead of managing metadata for a massive amount of small key-value items rises to an unbearable level. Put it simply, the current fine-grained, heavy-cost approach cannot continue to scale. In this paper, we have performed an experimental study on the scalability challenge of the current key-value cache system design and quantitatively analyzed the inherent issues related to the metadata operations for cache management. We further propose a key-value cache management scheme, called Catalyst , based on a highly efficient metadata structure, which allows us to make effective caching decisions in a scalable way. By offloading non-essential metadata operations to GPU, we can further dedicate the limited CPU and memory resources to the main service operations for improved throughput and latency. We have developed a prototype based on Memcached. Our experimental results show that our scheme can significantly enhance the scalability and improve the cache system performance by a factor of up to 4.3.

With the rapid advancement in edge computing, a recent trend is to migrate data processing from data centers to the edge to avoid long data transmission latencies. Databases, as an indispensable component, play a crucial role in efficient data management on edge devices. However, a critical limitation of edge devices is the highly constrained energy resource. Databases often incur a heavy load of CPU and storage I/O activities, which raises a particular concern on power-constrained platforms. In this paper, we have conducted an experimental study on the energy consumption of three representative databases, namely SQLite, LevelDB, and MongoDB, on single board computers for edge computing. We find that by deploying an appropriate database according to specific scenarios, the energy consumption can be reduced by a factor of 58.3, and the bandwidth can be improved by a factor of 54.4. Based on our experimental results, we also present several important system implications associated with our findings. We hope our first-hand data and the obtained insight can provide useful guidance for database and edge system designers and practitioners to develop and deploy energy-efficient databases for edge computing.

Time-series databases are becoming an indispensable component in today's data centers. In order to manage the rapidly growing time-series data, we need an effective and efficient system solution to handle the huge traffic of time-series data queries. A promising solution is to deploy a high-speed, large-capacity cache system to relieve the burden on the backend time-series databases and accelerate query processing. However, time-series data is drastically different from other traditional data workloads, bringing both challenges and opportunities. In this paper, we present a flash-based cache system design for time-series data, called TSCache . By exploiting the unique properties of time-series data, we have developed a set of optimization schemes, such as a slab-based data management, a two-layered data indexing structure, an adaptive time-aware caching policy, and a low-cost compaction process. We have implemented a prototype based on Twitter's Fatcache. Our experimental results show that TSCache can significantly improve client query performance, effectively increasing the bandwidth by a factor of up to 6.7 and reducing the latency by up to 84.2%.

In today's data centers, memory-based key-value systems, such as Memcached and Redis, play an indispensable role in providing high-speed data services. The rapidly growing capacity and quickly falling price of DRAM memory in the past years have enabled us to create a large memory-based key-value store, which is able to serve hundreds of Gigabytes to even Terabytes of key-value data all in memory. Unfortunately, CPU cache in modern processors has not seen a similar growth in capacity, still remaining at the level of a few dozens of Megabytes. Such an extremely low cache-to-memory ratio (less than 0.1%) poses a significant new challenge---the limited CPU cache is becoming a severe performance bottleneck that hinders us from fully exploiting the great potential of high-speed memory-based key-value stores. To address this critical challenge, we propose a highly cache-efficient scheme, called Cavast , to optimize the cache utilization of large-capacity in-memory key-value stores. Our goal is to maximize cache efficiency and system performance without any hardware changes. We first present two light-weight, software-only mechanisms to enable user to indirectly control the cache content at application level. Then we propose a set of optimization policies to address several critical design issues that impair cache's efficacy in the current key-value store systems. By carefully reorganizing the data layout in memory, redesigning the hash indexing structure, and offloading garbage collection, we can effectively improve the utilization of the limited cache space. We have developed a module in Linux as a kernel-level support, and implemented two prototypes based on Memcached and Redis with the proposed Cavast scheme. Our experimental studies show promising results. On a 6-core Intel Xeon processor with only 15-MB cache, we can raise the cache hit ratio up to 82.7% with a very small cache-to-memory ratio (0.023%), and significantly increase the key-value system throughput by a factor of up to 4.2.

The fast-pace advancement of flash technology has enabled us to build a very large-capacity cache system at a low cost. However, the reliability of flash devices still remains a non-negligible concern, especially for flash-based cache. This is for two reasons. First, corruption of dirty data in cache would cause a permanent loss of user data. Second, warming up a huge-capacity cache would take an excessively long period of time. In this paper, we present a highly reliable, efficient, object-based flash cache, called Reo. Reo is designed to leverage the highly expressible object interface to exploit the rich semantic knowledge of the flash cache manager. Reo has two key mechanisms, differentiated data redundancy and differentiated data recovery, to make a flash cache highly reliable, and in the meantime, still remains space efficient for high cache hit ratio. We have prototyped Reo based on open-osd, an open-source implementation of T10 Object Storage Device (OSD) in Linux. Our experimental results show that compared to uniform data protection, Reo achieves graceful performance degradation and prioritized recovery upon device failures. Compared to full replication, Reo is more space efficient and delivers up to 3.1 times of the cache hit ratio and up to 3.6 times of the bandwidth.

Flash-based key-value caching plays an important role in Internet services. Compared to in-memory key-value caches, flash-based key-value caches can provide a 10 to 100 times larger cache space, allowing to accommodate more data for a higher hit ratio. However, the current design relies on a simple hash-based indexing structure, which maintains the entire mapping table in DRAM memory. As the cache capacity continues to grow, such an "all-in-memory" approach raises concerns on cost, power, and scalability.

We herein build a smart parking system for large-scale underground parking lot in China, and deal with scheduling problems for multiple automatic guided vehicles (AGVs). In previous studies, multiple AGVs usually were scheduled in warehouse system, workshop system, etc. There was little report about AGVs in smart parking. In underground parking lot, designing maximum layout of parking space led to limited and double pathway for AGVs. Therefore, we proposed a dynamic time-window based on scheduling method (DTWS for short). In our DTWS, each AGV can dynamically adjust the path according to a time window, and thus implement the conflict-free pathway of AGVs. Finally, the experimental results showed that the our method solved the scheduling problems such as deadlock of multiple AGVs, and our parking system had an improved performance.

High-radix routers with low latency and high bandwidth play an increasingly important role in the design of large-scale interconnection networks such as those used in super-computers and datacenters. The tile-based crossbar approach partitions a single large crossbar into many small tiles and can considerably reduce the complexity of arbitration while providing throughput higher than the conventional switch implementation. However, it is not scalable due to power consumption, placement, and routing problems. In this paper, we propose a truly scalable router microarchitecture called Multiport Binding Tile-based Router (MBTR). By aggregating multiple physical ports into a single tile a high-radix router can be flexibly organized into a different array of tiles, thus the number of tiles and hardware overhead can be considerably reduced. Compared with a hierarchical crossbar, MBTR achieves up to 50%~75% reduction in memory consumption as well as wire area. Simulation results demonstrate MBTR is indistinguishable from the YARC router in terms of throughput and delay, and can even outperform it by reducing potential contention for output ports. We have fabricated an ASIC MBTR chip with 28nm technology. Internally, it runs at 700MHz and 30ns latency without any speedup. We also discuss how the microarchitecture parameters of MBTR can be adjusted based on the power, area, and design complexity constraints of the arbitration logic.

Interconnect network plays an important role in high performance computing systems. And its manageability directly affects the RAS (i.e., Reliability, Availability, and Serviceability) of the whole system. The Tianhe-2 system located in NSCC-gz (i.e., National Supercomputing Center of China in Guangzhou) uses proprietary interconnect network, which includes 5,856 high-radix network router chips (i.e., NRC) and 18,304 network interface chips (i.e., NIC). For such a very large-scale interconnect network, it is a great challenge to manage (such as configure, monitor, and debug) the numerous network chips and its network ports in an efficient way. By implementing the in-band management with very few hardware resources, the interconnect network in Tianhe-2 system achieves a highly efficient network management. In this paper, we introduce the design and implementation of the in-band management for interconnect network in Tianhe-2 system, especially emphasizing on several key features, including the set of achieved management functionalities, the architecture of network management, the format of management packets, the data flow and processing of management packets, etc. In this paper, we also evaluate the performance of in-band management by mainly comparing with out-band management scheme. The preliminary results demonstrate the efficiency of the in-band management for interconnect network in Tianhe-2 system.

Last-Level Cache (LLC) plays an important role in Chip Multi-Processor (CMP). The objective of this work is to optimize the structure and management strategy of LLC. Based on 8-core CMP, a LLC structure based on grouped cores is proposed, where 8 cores are divided into 4 groups. All LLC resources are classified into three types, which are fixed private cache, dynamic private cache and dynamic shared cache. The layout of the LLC structure and the corresponding dynamic partitioning strategy are designed to achieve low access latency and high efficiency. Experimental results on full-system simulator suggest that the proposed structure and method are able to reduce the access latency by 2% to 12% compared with previous works, such as tiled structure, cache-centered structure and core-centered structure. Consequently, performance measured by IPC is improved up to 7%. The contribution of this paper is useful for CMP performance, and applies to not only 8-core CMP but also all small-scale CMPs.

Turn-model is a classical method for designing partially adaptive routing algorithms without virtual channels, and can also be the basis of fully adaptive routing algorithms. We propose a novel scheme, Selective Extension of Routing Algorithms based on turn model (SERA), which alleviates restrictions on turn and path selections if possible without adding any new buffers or virtual channels. SERA can improve adaptivity of the original routing algorithms, and maintain the deadlock-free property. Thus, SERA is an important extension of the previous turn model theory. To present the effectiveness of SERA in adaptive algorithms, we redesign two existing routing algorithms, Odd-Even and LEAR. Simulation results show that the SERA scheme achieves an average delay reduction of 6% compared to the original routing algorithms.

Fat-tree topology is very popular for constructing interconnect network for data centers. Routing is one of the most important design issues of data center networks. Several routing algorithms have been proposed for fat-tree topology, but they all ignore the fault diagnosis problem. In order to facilitate the diagnosis of link-fault in fat-tree based networks, in this paper we propose the FT-BTR, a back-track routing algorithm for fat-tree which constrains both the routing path from the source processing node to the destination processing node and the routing path from destination processing node to source processing node use the same physical links set. Since the two and three stage fat-trees are the most common used, we further provide a detailed description of FT-BTR2 and FT-BTR3 routing algorithms, respectively. The theoretically analysis results show that the FT-BTR algorithm not only guarantee the back-track characteristic for routing between any two processing nodes, which can directly benefits the link fault diagnosis in interconnection networks, but also is load balanced and free of deadlock.

Continuing growth in traffic, the size of routing table as well as the link speeds puts great challenge on the performance of Internet address lookup. The packet forwarding engine need perform 150 million IP address lookups per second for a 100Gbps line card while accommodating up to 500,000 prefixes and very likely 1M in the near future. TCAM based lookup solutions do not scale well for the next-generation due to its high power dissipation and large footprint. Algorithmic solutions can achieve high throughputs with hardware parallelism and compact storage needs, but can hardly scale simultaneously in the three dimensions of increased table size, throughput, and prefix length as IP moves to 64 bit IPv6 addresses. We propose a novel IPv6 lookup algorithm called Prefix Range Based Binary Search (PRB-BS) using binary search over hash tables organized by the range of prefix length. By eliminating the path information of the subtrie our scheme reduces the memory demands considerably. Besides, the binary search scheme based on prefix range reduces the worst case time of hash lookups to log2L, with L being the number of subtrie layers. We also introduce asymmetry binary search to further reduce memory demands and memory accesses. Compared with the tree bitmap algorithm widely used by many modern routers the memory requirements of PRB-BS algorithm is about 55% of the tree bitmap algorithm. The experiment results also show that the average search depth of PRB-BS algorithm is stable at 2 with the increased number of prefixes, which reflects better scalability of PRB-BS algorithm.

In this paper, we propose a novel multi-VC dynamically shared buffer named DAMQ-PF for network on chip to decrease the memory and area requirement of statically allocating shared buffer among multiple virtual channels (VC). A small prefetch buffer is used for each VC to store data read from the shared buffer in advance. The same mechanism is also used in the implementation of idle address list. By so doing, we implement continuous and concurrent reading and writing of the shared buffer without delay. A fair credit management method is also proposed to avoid a single VC occupying the shared buffer exclusively. Analyses and tests show that DAMQ-PF achieves high buffer utilization, low write and read delay and high throughput which satisfies the performance requirement of NoC based on flit switch very well.

Complementary synthesis can automatically synthesize the decoder circuit of an encoder. However, its user needs to manually specify an assertion on some configuration pins to prevent the encoder from reaching the nonworking states. To avoid this tedious task, this paper propose an automatic approach to infer this assertion, by iteratively discovering and removing cases without decoders. To discover all decoders that may exist simultaneously under this assertion, a second algorithm based on functional dependency is proposed to decompose , the Boolean relation that uniquely determines the encoder's input, into all possible decoders. To help the user select the correct decoder, a third algorithm is proposed to infer each decoder's precondition formula, which represents those cases that lead to this decoder's existence. Experimental results on several complex encoders indicate that our algorithm can always infer assertions and generate decoders for them. Moreover, when multiple decoders exist simultaneously, the user can easily select the correct one by inspecting their precondition formulas.

Current research and trends reveals that high-radix switches can remarkably lower down the network diameter and switch count of interconnection network in high performance computers, and it is much valuable in saving packet latency, cost and power consumption. HOL blocking limits the throughput of an N×N crossbar to less than 58% and this can be even worse in high radix switches because most technologies claimed as could eliminate HOL blocking cannot be scalable to high radix switches. In this paper, a new efficient architecture for high-radix switches is proposed. The architecture, referred to as Hierarchical Asymmetric Crossbar (HAC), relies on one simple but important fact that in an asymmetric crossbar, which input ports much less than output ports, effect of HOL blocking on crossbar throughput is very low or negligible. Thus a HAC architecture N×N high radix switch can be divided into two levels, the first level includes N/m smaller m×N asymmetric crossbars, and the second level includes N small N/m×1 multiplexer. A 32×32 HAC high radix switch prototype, based on 4×32 asymmetric small crossbars, is introduced in the paper. Clock cycle simulation reveals that in such a switch the impact of HOL blocking is nearly all eliminated and the switch throughput can be as high as 94%.

FAST TCP is a new transmission control protocol designed for high speed networks. In this paper, we mainly address the stability issue of FAST TCP with time-delay. We first establish the nonlinear delay differential model of the transmission system made up of FAST TCP and the routers. Then, using the stability criterion for double time-delay system, we give the local stability condition of FAST TCP in single-link multi-source networks with time-delay. The conclusion gained here is more accurate than the existing one. Based on the stability conclusion, we further discuss the parameter setting of FAST TCP and propose a method to adjust the parameter. The simulation results confirm the correctness of the conclusion and the effectiveness of the new algorithm.

Complementary synthesis automatically synthesizes the decoder circuit of an encoder. It determines the existence of the decoder by checking whether the encoder's input can be uniquely determined by its output. However, this algorithm will not halt if the decoder does not exist. To solve this problem, a novel halting algorithm is proposed. For every path of the encoder, this algorithm first checks whether the encoder's input can be uniquely determined by its output. If yes, the decoder exists; otherwise, this algorithm checks if this path contains loops, which can be further unfolded to prove the non-existence of the decoder for all those longer paths. To illustrate its usefulness and efficiency, this algorithm has been run on several complex encoders, including PCI-E and Ethernet. Experimental results indicate that this algorithm always halts properly by distinguishing correct encoders from incorrect ones, and it is more than three times faster than previous ones.

One of the most difficult jobs in designing communication and multimedia chips is to design and verify the complex complementary circuit pair (E,E-1), in which circuit E transforms information into a format suitable for transmission and storage, and its complementary circuitE-1recovers this information. In order to facilitate this job, we proposed a novel two-step approach to synthesize the complementary circuitE-1fromEautomatically. First, a SAT solver was used to check whether the input sequence ofEcan be uniquely determined by its output sequence. Second, the complementary circuitE-1was built by characterizing its Boolean function, with an efficient all-solution SAT solver based on discovering XOR gates and extracting unsatisfiable cores. To illustrate its usefulness and efficiency, we ran our algorithm on several complex encoders from industrial projects, including PCIE and 10 G Ethernet, and successfully built correct complementary circuits for them.

This paper addresses multicast routing in 40 Gb/s traffic in heterogeneous optical networks. The multicast routing of multi-rate traffic (MRMT) problem is informally defined as the process of finding the best routing which maximizes the total bandwidth utilization in the network, for a given set of sessions, and a given WDM and TDM equipment budget. In our model, a multicast connection is realized by constructing a multicast tree. The whole process is divided into two steps. Numerical results demonstrate our approach utilizes network resources more efficiently, as compared to the approach based on shortest path algorithm.

Although a lot of previous work on schema matching has developed many partial automatic matches for specific application domains, combining multiple match techniques enables achieving high accuracy for a large variety of match circumstances. In this context, we present a schema-based element matching approach that concatenates linguistic-based matchers and a constraint-based matcher. We propose a basic processing of our element level match approach in terms of a sequence of linguistic-based match and constraint-based match. We also provide a composite element name matcher to automatically combine linguistic-based match algorithms with a maximum priority strategy, and a neural network matcher to categorize elements of schemas by using element constraints with results from composite name matcher for joint consideration of multiple criteria. The concatenation of composite name matcher and neural network matcher enable our approach to adapt to more complex matching circumstance