Ubiquitous computing and the upcoming broadcast-and-communication convergence require networks that provide very complex services. In particular, networks are needed that can service several users or terminals at various times or places with various application-layer functions that can be changed at a high response speed by adding high-speed processing at the network edge. I present a query-transaction acceleration appliance that uses a dynamic reconfigurable processor (DRP) and enables high-speed stateful packet-by-packet self-reconfiguration to achieve that requirement. This appliance processes at high speeds, has flexible application layer functions that are changeable with a high-speed response, and uses direct packet I/O bypassing memory, hierarchical interconnection of processors, and stateful packet-by-packet self-reconfiguration. In addition, the DRP enables the fabrication of a compact and electric-power-saving appliance. I made a prototype and implemented several transport/application layer functions, such as TCP connection control, auto-caching of server files, uploading cache data for server, and selection/insertion/deletion/update of data for a database. In an experimental evaluation in which four kinds of query-transactions were continually executed in order, I found that the appliance achieved four functions changeable at a high response speed (within 1 ms), and a processing speed (2,273 transactions/sec.) 18 times faster than a PC with a 2-GHz processor.

A temporal correlation based port combination algorithm that customizes the router design in Network-on-Chip (NoC) is proposed for reconfigurable systems in order to minimize required hardware amount. Given the traffic characteristics of the target application and the expected hardware amount reduction rate, the algorithm automatically makes the port combination plan for the networks. Since the port combination technique has the advantage of almost keeping the topology including two-surface layout, it does not affect the design of the other layer, such as task mapping and scheduling. The algorithm shows much better efficiency than the algorithm without temporal correlation. For the multimedia stream processing application, the algorithm can save 55% of the hardware amount without performance degradation, while the none temporal correlation algorithm suffers from 30% performance loss.

The present paper describes an implementation of an intrusion detection system (IDS) on an FPGA for 10 Gigabit Ethernet. The system includes an exact string matching circuit for 1,225 Snort rules on a single device. A number of studies have examined string matching circuits for IDS. However, implementing a circuit that processes a large rule set at high throughput is difficult. In a previous study, we proposed a method for generating an NFA-based string matching circuit that has expandability of processing data width and drastically reduced resource requirements. In the present paper, we implement an IDS circuit that processes 1,225 Snort rules at 10 Gbps with a single Xilinx Virtex-II Pro xc2vp-100 using the NFA-based method. The proposed circuit also provides packet filtering for an intrusion protection system (IPS). In addition, we developed a tool for automatically generating the Verilog HDL source code of the IDS circuit from a Snort rule set. Using the FPGA and the IDS circuit generator, the proposed system is able to update the matching rules corresponding to new intrusions and attacks. We implemented the IDS circuit on an FPGA board and evaluated its accuracy and throughput. As a result, we confirmed in a test that the circuit detects attacks perfectly at the wire speed of 10 Gigabit Ethernet.

This paper presents a self-reconfigurable adaptive FIR filter system design using dynamic partial reconfiguration, which has flexibility, power efficiency, advantages of configuration time allowing dynamically inserting or removing adaptive FIR filter modules. This self-reconfigurable adaptive FIR filter is responsible for providing the best solution for realization and autonomous adaptation of FIR filters, and processes the optimal digital signal processing algorithms, which are the low-pass, band-pass and high-pass filter algorithms with various frequencies, for noise removal operations. The proposed stand-alone self-reconfigurable system using Xilinx Virtex4 FPGA and Compact-Flash memory shows the improvement of configuration time and flexibility by using the dynamic partial reconfiguration techniques.

Multiple sequence alignment problems in computational biology have been focused recently because of the rapid growth of sequence databases. By computing alignment, we can understand similarity among the sequences. Many hardware systems for alignment have been proposed to date, but most of them are designed for two-dimensional alignment (alignment between two sequences) because of the complexity to calculate alignment among more than two sequences under limited hardware resources. In this paper, we describe a compact system with an off-the-shelf FPGA board and a host computer for more than three-dimensional alignment based on dynamic programming. In our approach, high performance is achieved (1) by configuring optimal circuit for each dimensional alignment, and (2) by two phase search in each dimension by reconfiguration. In order to realize multidimensional search with a common architecture, two-dimensional dynamic programming is repeated along other dimensions. With this approach, we can minimize the size of units for alignment and achieve high parallelism. Our system with one XC2V6000 enables about 300-fold speedup as compared with single Intel Pentium4 2 GHz processor for four-dimensional alignment, and 100-fold speedup for five-dimensional alignment.

This paper describes a new design concept, the Body Bias Voltage Set (BBVS), and presents the effect of the BBVS on static power, operating speed, and area overhead in an FPGA with field-programmable V_th components. A Flex Power FPGA is an FPGA architecture to solve the static power problem by the fine grain field-programmable V_th control method. Since the V_th of transistors for specific circuit blocks in the Flex Power FPGA is chosen from a set of V_th values defined by a BBVS, selection of a particular BBVS is an important design decision. A particular BBVS is chosen by selecting body biases from among several supplied body bias candidates. To select the optimal BBVS, we provide 136 BBVSs and perform a thorough search. In a BBVS of less V_th steps, the deepest reverse body bias for high-V_th transistors does not necessarily result in optimal conditions. A BBVS of 0.0 V and -0.8 V, which requires 1.65 times the original area, utilizes as little as 1/30 of the static power of a conventional FPGA without performance degradation. Use of an aggressive forward body bias voltage such as +0.6 V for lowest-V_th, performance is increased by up to 10%. Another BBVS of +0.6 V, 0.0 V, and -0.8 V reduces static power to 14.06% while maintaining a 10% performance increase, but it requires 2.75-fold area.

Extracting frequently executed (hot) portions of the application and executing their corresponding data flow graph (DFG) on the hardware accelerator brings about more speedup and energy saving for embedded systems comprising a base processor integrated with a tightly coupled accelerator. Extending DFGs to support control instructions and using Control DFGs (CDFGs) instead of DFGs results in more coverage of application code portion are being accelerated hence, more speedup and energy saving. In this paper, motivations for extending DFGs to CDFGs and handling control instructions are introduced. In addition, basic requirements for an accelerator with conditional execution support are proposed. Then, two algorithms are presented for temporal partitioning of CDFGs considering the target accelerator architectural constraints. To demonstrate effectiveness of the proposed ideas, they are applied to the accelerator of a reconfigurable processor called AMBER. Experimental results approve the remarkable effectiveness of covering control instructions and using CDFGs versus DFGs in the aspects of performance and energy reduction.

For a coarse grain dynamic reconfigurable processing unit cooperating with a general purpose processor, a context selection method, which can reduce total execution cycles of a given program, is proposed. The method evaluates context candidates from a given program, in terms of reduction in cycles by exploiting parallel and pipeline execution of the reconfigurable processor. According to this evaluation measure, the method selects appropriate contexts for the dynamic reconfigurable processing unit. The proposed method is implemented on the framework of COINS project. For several example programs, the generated codes are evaluated by a software simulator in terms of execution cycles, and these results prove the effectiveness of the proposed method.

In these days, many dynamically reconfigurable architectures have been introduced to fill the gap between ASICs and software-programmed processors such as GPPs and DSPs. These reconfigurable architectures have shown to achieve higher performance compared to software-programmed processors. However, reconfigurable architectures suffer from a significant reconfiguration overhead and a speedup limitation. By reducing the reconfiguration overhead, the overall performance of reconfigurable architectures can be improved. Therefore, we will describe temporal partitioning, which are able to amortize the reconfiguration overhead at synthesis phase or compilation time. Our temporal partitioning methodology splits a configuration context into temporal partitions to amortize reconfiguration overhead. And then, we will present benchmark results to demonstrate the effectiveness of our methodology.

High power consumption is a constraining factor for the growth of programmable logic devices. We propose two techniques in order to reduce power consumption. The first is a technique for creating contexts. This technique uses data-dependent circuits and wire sharing between contexts. The second is a technique for switching the contexts. In this paper, we evaluate the capability of the two techniques to reduce power consumption using a multi-context logic device. As a result, as compared with the original circuit, our multi-context circuits reduced the power consumption by 9.1% on an average and by a maximum of 19.0%. Furthermore, applying our resource sharing technique to these circuits, we achieved a reduction of 10.6% on an average and a maximum reduction of 18.8%.

We describe a new ultrasonography system, which can identify an implant position in bone. Although conventional X-ray fluoroscopy can visualize implants, it has the serious disadvantage of X-ray exposure. Therefore, we developed a system for orthopedic surgery that involves no X-ray exposure. Barriers to the development of the system were overcome using an ultrasonic instrument and fuzzy logic techniques. We located distal transverse screw holes in an intramedullary nail during surgery for femur fracture. The screw hole positions are identified by calculating two fuzzy degrees of intensity and the variance. Results allow this system to identify the screw hole positions within an error of 1.43 mm, an error ratio adequate for clinical surgical practice.

The link structure of the Web is generally viewed as the webgraph. Web structure mining is a research area that mainly aims to find hidden communities by focusing on the webgraph, and communities or their cores are supposed to constitute dense subgraphs. Therefore, structure mining can actually be realized by enumerating such substructures, and Kleinberg's biclique model is well-known among them. In this paper, we examine some candidate substructures, including conventional bicliques, and attempt to find useful information from the real web data. Especially, we newly exploit isolated cliques for our experiments of structure mining. As a result, we discovered that isolated cliques that lie over multiple domains can stand for useful communities, which implies the validity of isolated clique as a candidate substructure for structure mining. On the other hand, we also observed that most of isolated cliques on the Web correspond to menu structures and are inherent in single domains, and that isolated cliques can be quite useful for detecting harmful link farms.

Normalization transform is known to be very useful for finding the overall trend of time-series data since it enables finding sequences with similar fluctuation patterns. Previous subsequence matching methods with normalization transform, however, would incur index overhead both in storage space and in update maintenance since they should build multiple indexes for supporting query sequences of arbitrary length. To solve this problem, we adopt a single-index approach in the normalization-transformed subsequence matching that supports query sequences of arbitrary length. For the single-index approach, we first provide the notion of inclusion-normalization transform by generalizing the original definition of normalization transform. To normalize a window, the inclusion-normalization transform uses the mean and the standard deviation of a subsequence that includes the window while the original transform uses those of the window itself. Next, we formally prove the correctness of the proposed normalization-transformed subsequence matching method that uses the inclusion-normalization transform. We then propose subsequence matching and index-building algorithms to implement the proposed method. Experimental results for real stock data show that our method improves performance by up to 2.52.8 times compared with the previous method.

Exploiting layer7 context is an effective approach to improving the accuracy of detecting malicious messages in network intrusion detection/prevention systems (NIDS/NIPSs). Layer7 context enables us to inspect message formats and the message exchanged order. Unfortunately, layer7-aware NIDS/NIPSs pose crucial implementation issues because they require full TCP and IP reassembly without losing 1) complete prevention, 2) performance, 3) application transparency, or 4) transport transparency. Complete prevention means that the NIDS/NIPS should prevent malicious messages from reaching target applications. Application transparency means not requiring any modifications to and/or reconfiguration of server and client applications. Transport transparency is not to disrupt the end-to-end semantics of TCP/IP. To the best of our knowledge, none of the existing approaches meet all of these requirements. We have developed an efficient mechanism for layer7-aware NIDS/NIPSs that does meet the above requirements. Our store-through does this by forwarding each out-of-order or IP-fragmented packet immediately after copying the packet even if it has not been checked yet by an NIDS/NIPS sensor. Although the forwarded packet might turn out to be a part of an attack message, the store-through mechanism can successfully defend against the attack by blocking one of the subsequent packets that contain another part of attack message. Testing of a prototype in Linux kernel 2.4.30 demonstrated that the overhead of our mechanism is negligible compared with that of a simple IP forwarder even with the presence of out-of-order and IP-fragmented packets. In addition, the experimental results suggest that the CPU and memory usage incurred by our store-through is not significant.

Our purpose is to estimate conditional probabilities of output labels in multiclass classification problems. Adaboost provides highly accurate classifiers and has potential to estimate conditional probabilities. However, the conditional probability estimated by Adaboost tends to overfit to training samples. We propose loss functions for boosting that provide shrinkage estimator. The effect of regularization is realized by shrinkage of probabilities toward the uniform distribution. Numerical experiments indicate that boosting algorithms based on proposed loss functions show significantly better results than existing boosting algorithms for estimation of conditional probabilities.

We extend the framework of cost-sensitive classification to mitigate risks of huge costs occurring with low probabilities, and propose an algorithm that achieves this goal. Instead of minimizing the expected cost commonly used in cost-sensitive learning, our algorithm minimizes conditional value-at-risk, also known as expected shortfall, which is considered a good risk metric in the area of financial engineering. The proposed algorithm is a general meta-learning algorithm that can exploit existing example-dependent cost-sensitive learning algorithms, and is capable of dealing with not only alternative actions in ordinary classification tasks, but also allocative actions in resource-allocation type tasks. Experiments on tasks with example-dependent costs show promising results.

This paper proposes a simple, efficient method that, based on increasing the differences between two neighboring pixels, losslessly embeds a message into a host image. The point at which the number of pixel differences in the image is at a maximum is selected to embed the message. The selected difference is increased by 1 or left unchanged if the embedded bit is "1" or "0", respectively. On the other hand, differences larger than the selected difference are increased by 1. Increasing a difference is done by adding 1 to or subtracting 1 from the pixel if its value is larger or smaller than its preceding pixel, respectively. Experimental results show that the proposed method can achieve a high payload capacity while the image distortion of the stego-image remains minimal.

Most learning-based super-resolution methods neglect the illumination problem. In this paper we propose a novel method to combine blind single-frame super-resolution and shadow removal into a single operation. Firstly, from the pattern recognition viewpoint, blur identification is considered as a classification problem. We describe three methods which are respectively based on Vector Quantization (VQ), Hidden Markov Model (HMM) and Support Vector Machines (SVM) to identify the blur parameter of the acquisition system from the compressed/uncompressed low-resolution image. Secondly, after blur identification, a super-resolution image is reconstructed by a learning-based method. In this method, Logarithmic-wavelet transform is defined for illumination-free feature extraction. Then an initial estimation is obtained based on the assumption that small patches in low-resolution space and patches in high-resolution space share a similar local manifold structure. The unknown high-resolution image is reconstructed by projecting the intermediate result into general reconstruction constraints. The proposed method simultaneously achieves blind single-frame super-resolution and image enhancement especially shadow removal. Experimental results demonstrate the effectiveness and robustness of our method.

This paper addresses a new surface reconstruction scheme for approximating the isosurface from a set of tomographic cross sectional images. Differently from the novel Marching Cubes (MC) algorithm, our method does not extract the iso-density surface (isosurface) directly from the voxel data but calculates the iso-density point (isopoint) first. After building a coarse initial mesh approximating the ideal isosurface by the cell-boundary representation, it metamorphoses the mesh into the final isosurface by a relaxation scheme, called shrink-wrapping process. Compared with the MC algorithm, our method is robust and does not make any cracks on surface. Furthermore, since it is possible to utilize lots of additional isopoints during the surface reconstruction process by extending the adjacency definition, theoretically the resulting surface can be better in quality than the MC algorithm. According to experiments, it is proved to be very robust and efficient for isosurface reconstruction from cross sectional images.

This paper proposes a method for reinforcing noun countability prediction, which plays a crucial role in demarcating correct determiners in machine translation and error detection. The proposed method reinforces countability prediction by introducing a novel heuristics called one countability per discourse. It claims that when a noun appears more than once in a discourse, all instances will share identical countability. The basic idea of the proposed method is that mispredictions can be corrected by efficiently using one countability per discourse heuristics. Experiments show that the proposed method successfully reinforces countability prediction and outperforms other methods used for comparison. In addition to its performance, it has two advantages over earlier methods: (i) it is applicable to any countability prediction method, and (ii) it requires no human intervention to reinforce countability prediction.

This paper describes a modified ICP registration system of facial point data with range-scanning equipment for medical Augmented Reality applications. The reference facial point data are extracted from the pre-stored CT images; the floating facial point data are captured from range-scanning equipment. A modified soft-shape-context ICP including an adaptive dual AK-D tree for searching the closest point and a modified shape-context objective function is used to register the floating data to reference data to provide the geometric relationship for a medical assistant system and pre-operative training. The adaptive dual AK-D tree searches the closest-point pair and discards insignificant control coupling points by an adaptive distance threshold on the distance between the two returned closest neighbor points which are searched by using AK-D tree search algorithm in two different partition orders. In the objective function of ICP, we utilize the modified soft-shape-context information which is one kind of projection information to enhance the robustness of the objective function. Experiment results of using touch and non-touch capture equipment to capture floating point data are performed to show the superiority of the proposed system.

Given a set of strings U = {T₁, T₂, ...,T}, the longest common repeat problem is to find the longest common substring that appears at least twice in each string, considering direct, inverted, and mirror repeats. We define the generalised longest common repeat problem and present a linear time solution.

In this paper, we describe a method of applying Collaborative Filtering with a Machine Learning technique to predict users' preferences for clothes on online shopping malls when user history is insufficient. In particular, we experiment with methods of predicting missing values, such as mean value, SVD, and support vector regression, to find the best method and to develop and utilize a unique feature vector model.

Recently, many studies reported various advanced e-Health service systems in patient care monitoring utilizing sensor networks and questionnaire systems. We propose an informant driven e-Health service system for the identification of heart rate related mental stress factors with a simple operation of informant-client model. Through performance analysis, we show that the proposed system is a cost-effective stress identification system applicable to mobile wireless networks.

In this paper, we propose a multipath en-route filtering method to deal with the problems caused by black hole attacks and selective forwarding attacks. Our result shows that the method is more resilient to these problems up to a certain number of compromised nodes than the statistical en-route filtering scheme.

Recently, many techniques have been proposed to improve speaker identification in noise environments. Among these techniques, we consider the feature recombination technique for the multi-band approach in noise robust speaker identification. The conventional feature recombination technique is very effective in the band-limited noise condition, but in broad-band noise condition, the conventional feature recombination technique does not provide notable performance improvement compared with the full-band system. Even though the speech is corrupted by the broad-band noise, the degree of the noise corruption on each sub-band is different from each other. In the conventional feature recombination for speaker identification, all sub-band features are used to compute multi-band likelihood score, but this likelihood computation does not use a merit of multi-band approach effectively, even though the sub-band features are extracted independently. Here we propose a new technique of sub-band likelihood computation with sub-band weighting in the feature recombination method. The signal to noise ratio (SNR) is used to compute the sub-band weights. The proposed sub-band-weighted likelihood computation makes a speaker identification system more robust to noise. Experimental results show that the average error reduction rate (ERR) in various noise environments is more than 24% compared with the conventional feature recombination-based speaker identification system.