On privacy protection data publication targeting dynamic data, a privacy issue for the generalization property called m-invariance has been pointed out. In this paper, we propose an information alteration method to overcome this issue.

Bitcoin is one of the typical cryptocurrencies. Cur-rently, Bitcoin allows unilateral sending of currency by the sender (payer of currency) regardless of the presence or absence of intention of the recipient (payee of currency). Previous works pointed out that this could induce the sending of currency used in crimes, etc., which could lead to problems. This problem is called the recipient unapproved problem. Bitcoin users use a function called Bitcoin wallet in the platform software such as Bitcoin Core to perform transactions. In this paper, we try to incorporate a new transaction creation method into the Bitcoin wallet in order to resolve the recipient unapproved problem. The new transaction creation method also allows the recipient's Bitcoin wallet to participate in the creation of the transaction, and adds the recipient's digital signature to prove that the transaction was also approved by the recipient and a new address that cannot be used except for approved transactions. In experiments for investigating the overhead of the new transaction creation method, results showed that a transaction can be created with about twice creation execution time of the conventional transaction creation method.

On information security area, it is important to guarantee data privacy, availability and integrity. Secret sharing schemes are known as technologies for protecting data privacy and attaining availability. In secret sharing schemes, n distributed informations of a secret value d, called as shares are constructed, and distributed those to n participants. Then, a group of t members for n participants reconstruct the secret value d by exchanging their shares each other. On the other hand, less than t shares cannot induce the secret value. Moreover, as secret sharing schemes for solving the issue for data integrity, there exist verifiable secret sharing schemes. In verifiable secret sharing schemes, we can also confirm the correctness of reconstructed secrets. In this paper, we focus on a previous verifiable secret sharing scheme and point out issues as necessity of multi-party computations to protect shares from malicious participants. Next, we propose a new verifiable secret sharing scheme without multi-party computations and prove the security of verifications by the proposed scheme.

In recent years, blockchain is known as a decentralized secure digital ledger of economic transactions. In this paper, we point out a new issue by abusing published information with relation to recipients on blockchain. Then, we propose a solution to our discovered issue.

In this paper, we propose some feature vectors that better represent characteristics of lithography hotspots for machine learning based hotspot detection. In the lithography process, which is one of the LSI fabrication processes, a local layout pattern with a high failure probability is called a hotspot. It is desirable to find and remove such hotspots before starting the fabrication processes, since the reproduction of photomasks for LSI fabrication takes a huge cost. Our feature vectors consider distances between wires, which have a great effect on accuracies of images developed on a wafer, to efficiently find hotspots. Experimental results showed that our proposed feature vectors achieved lower undetected error probabilities compared to some existing ones including a well-known one.

This paper proposes an FPGA-based nearest neighbor search engine for high-dimensional data, in which nearest neighbor search is performed based on distance-based hashing. The proposed hardware search engine implements a nearest neighbor search algorithm based on an extension of flexible distance-based hashing (FDH, for short), which finds an exact solution with high probability. The proposed engine is a parallel processing and pipelined circuit so that search results can be obtained in a short execution time. Experimental results show the effectiveness and efficiency of the proposed engine.

With the recent explosive growth of data in the real world, data mining techniques to obtain characteristics and knowledge from big data attract more attention. This paper focuses on a method to detect outliers in streaming data, and proposes a fast FPGA implementation of outlier detection based on the Mahalanobis distance. The proposed circuit is fully pipelined, and in every clock cycle, a given sample data can be judged as an outlier or not. Experimental evaluation shows that the proposed circuit is 37 times faster than the software implementation of the Mahalanobis distance-based outlier detection.

Routing is one of the time-consuming processes in LSI design to connect previously placed terminals. In this study, we propose a multithreaded parallel routing algorithm for LSI design. In the proposed method, first, threads are created and the nets of the target net list are equally distributed to the threads. Sharing the routing regions, each of the threads searches a candidate path of a net in parallel without synchronization. Then, each thread exclusively writes a candidate path to the routing regions as a determined path. Although the exclusive control is necessary when updating the routing regions, this asynchronous parallel routing reduces the wait time of the threads. If a candidate path of a net does not satisfy constraints due to the asynchronous parallel routing, the net is re-routed. We experimentally confirmed that our proposed method running on a PC with eight cores was 7.1 times faster than the sequential execution. In addition, we also confirmed that the routing quality was not degraded compared to the sequential execution.

This paper proposes a method using partial re-configuration to realize a compact regular expression matching engine, which can update a pattern quickly. In the proposed method, several partial circuits, each of which handles a different class of regular expressions, are provided in advance. When a regular expression pattern is given, a suitable and compact matching engine is implemented on FPGA by combining the partial circuits according to the given pattern and using partial reconfiguration. The method can update a pattern quickly, since it does not need re-design of a circuit resulting in a long time for pattern update. Experimental results show that the proposed method reduces 63% circuit size of an existing engine without increasing pattern updating time.

This paper presents a design method for programmable two-variable discrete (real-valued) function generators based on a piecewise polynomial approximation. To approximate a given discrete function by polynomials efficiently, we propose a hybrid approximation method using both spline and bilinear interpolations. The proposed method can significantly reduce memory size needed to implement a two-variable discrete function by accepting a small approximation error, and thus it can be used to explore design space taking into account a trade-off between memory size and approximation error. Experimental results show that the proposed design method reduces 75% of memory size without losing circuit speed by accepting only 1% error, and the circuits designed by the proposed method achieve about 650 times greater throughput than their software programs. We can automatically synthesize such compact and fast function generators using the proposed design method.

In this paper, we propose a systolic pattern-independent hardware regular expression matching (REM) engine which handles nested Kleene operators used in virus patterns. Pattern-independent systolic REM engines are suitable to network intrusion detection systems for quick updating of virus pattern. In the proposed engine, we introduce a compact pattern-independent NFA circuit, which can handle any small regular expression patterns, into a systolic REM engine to handle nested Kleene operators. Experimental results show that the extended engine implemented on an FPGA handles nested Kleene operators with efficient circuit size and high performance (2.17 Gbps).

Text search is a procedure to find occurrences of a pattern in a given text where the pattern and each occurrence may have a limited number of differences. Text search is an indispensable technique for bibliographic databases. In this paper, a restricted class of regular expressions is used as patterns, and all substrings in a text that are close to a pattern, possibly with some errors, are located. We call this text search problem approximate regular expression matching. For this problem, a one-dimensional systolic algorithm is presented based on dynamic programming. Experiments show that the proposed hardware engine implemented on FPGA realizes high-speed text search.

This paper proposes a high-speed string matching circuit for searching a pattern in a given text. In the circuit, a pattern is specified by a class of restricted regular expressions. The architecture of the proposed circuit is a one-dimensional systolic architecture consisting of simple processing units. It can be effectively used for network intrusion detection systems (NIDSs).

In this paper, we propose a parallel algorithm to solve the quadratic assignment problem in a short execution time. The proposed algorithm is based on tabu search, and its main body is a systolic algorithm, which runs on a one-dimensional array of simple processing units. During the algorithm execution, multiple neighborhood solutions are evaluated in parallel and each solution is evaluated in a pipeline fashion. The proposed algorithm effectively utilizes internal block RAMs of recent large scale FPGAs. Experimental results show the efficiency and effectiveness of the proposed algorithm.

In this paper, we propose an FPGA implementation of tabu search to solve the quadratic assignment problem in a short execution time. In the proposed hardware implementation of tabu search, multiple neighbor solutions are evaluated in parallel and each solution is evaluated in a pipeline fashion. The proposed method effectively utilizes internal block RAMs of recent large scale FPGAs. Experimental results show the efficiency and effectiveness of the proposed method

In the high performance VLSI with multi-layer layout model, the complexity of the global routing problem becomes much high under timing constraints.This paper presents a hierarchical global routing method based on a multi-layer routing model for the high performance standard cell layout.In each hierarchical level, the routes of nets are determined by solving a linear programming problem considering wire-sizing and bufferinsertion under timing constraints.We have implemented the proposed method on a workstation and showed the effectiveness of the method from experimental results.

No abstract available.

In this paper, we propose an adaptive genetic algorithm (GA) to solve the floorplanning problem in VLSI layout design, in which the sequence-pair representation is adopted as the coding scheme of each chromosome. New genetic operators for the problem are presented to explore the search space efficiently. The proposed GA has an adaptive strategy which dynamically selects an appropriate genetic operator during the GA execution depending on the stare of an individual. Experimental results show the effectiveness of our adaptive genetic algorithm compared to simulated annealing (SA).

In this paper, we propose a genetic algorithm (GA) to solve the rectangular packing problem (RP), in which the sequence-pair representation is adopted as the coding scheme of each chromosome. New genetic operators for RP are presented to explore the search space efficiently. The proposed GA has an adaptive strategy which dynamically selects an appropriate genetic operator during the GA execution depending on the state of an individual. Experimental results show the effectiveness of our adaptive genetic algorithm compared to simulated annealing (SA).

This paper describes an LSI implementation of a genetic algorithm (GA), called the Genetic Algorithm Accelerator (GAA) chip. The GAA chip is an LSI implementation of a GA, in which two types of crossover operators are supported, and the operator to be actually used in the algorithm is not fixed in advance, but dynamically selected for each pair of chromosomes in the algorithm execution. The GAA chip has been designed with the Verilog HDL and simulated with some benchmark functions. According to the simulation, the GAA chip will run with a maximum 50 MHz clock. The chip has been fabricated with CMOS 0.5 /spl mu/m standard cell technology.

This paper presents a timing-driven global routing algorithm based on coarse pin assignment, block reshaping, and positioning for VLSI building block layout. As opposed to conventional approaches, we combine pin assignment and global routing problems into one problem. The proposed algorithm determines global routes, coarse pin assignments, and block shape and positions so as to minimize the chip area and total wire length of nets under the given timing constraints. It is based on an iterative improvement paradigm and performs rip-up and rerouting, block reshaping, and positioning in the manner of simulated evolution taking shapes of soft blocks and routing congestion into consideration until the solution is not improved. The Elmore delay model is adopted for the interconnection delay model. Experimental results show the effectiveness of the proposed algorithm.

In this paper, we present a parallel algorithm running on a shared memory multi-processor workstation for timing driven standard cell layout. The proposed algorithm is based on POPINS2.0 and consists of three phases. First, we get an initial placement by a hierarchical timing-driven mincut placement algorithm. At the top level of partitioning hierarchy, we perform one step of bi-partitioning by several processors, and in the lower levels of partitioning hierarchy, partitionings of each region in a level are performed in parallel. Next, in phase 2, iterative improvement of the sub-circuit which contains critical paths is performed by nonlinear programming. Parallel processing is realized by performing the nonlinear programming method to each sub-circuit in parallel. Finally, in phase 3, the placement is transformed to a row based layout style by a timing-driven row assignment method. We have implemented the proposed method on a 4CPU multi-processor workstation and showed that the proposed method is promising through experimental results.

In this paper, we will consider global routing and pin assignment in VLSI building block layout, and present an efficient algorithm which integrates global routing, pin assignment, block reshaping and positioning. The general flow of the proposed algorithm is the same as the one proposed in by Cong in 1991 [1] and consists of two main phases. The first phase is to determine not only global routes and coarse pin assignment in the same way as [1], but also shapes and positions of blocks. The second phase is to compute the final pin assignment for channels. We generalize the channel pin assignment (CPA) problem in [1], in which the CPA problem is formulated for only channels formed by two blocks, to the CPA problem for channels formed by multiple blocks. We will propose a linear time optimal channel pin assignment algorithm, which is an extension of the algorithm in [1]. Experimental results show the effectiveness of the proposed algorithm.

No abstract available.

In this paper, we present a new performance driven placement method based on path delay constraint approach for large standard cell layout. The proposed method consists of three phases and uses the Elmore delay model to model interconnection delay precisely in each phase. In the first phase, initial placement is performed by an efficient performance driven mincut partitioning method. Next, an iterative improvement method by nonlinear programming improves the layout. The improvement is formulated as the problem of minimizing the total wire length subject to critical path delays. Finally, row assignment considering timing constraint is performed. From the experimental results, the proposed method is much better than RITUAL in point of the maximal violation ratio, the total wire length, and the cut size, and is more effective in the interconnection delay model and its extendability.

No abstract available.

This paper presents an MCM routing algorithm considering crosstalk. The aim of the algorithm is to minimize the total wire length under the condition that the crosstalk constraints among nets are satisfied. Experimental results show the effectiveness of the algorithm.

In this paper, we present a formal verification method based on internal variables of a given circuit. In this method, the problem of deciding the logical equivalence of two logic circuits is transformed to the satisfiability problem, which is solved by constructing a set of BDDs, each of which is corresponding to an internal variable of the circuit. Experimental results showed the effectiveness of the proposed method.

Given an undirected graph G with n vertices, m edges and positive edge weights and k terminals {s/sub 1/, s/sub 2/, ..., s/sub k/} on G, the problem of computing a minimum k-way cut of G is to find a minimum (cost) k-way cut C that disconnects each terminal from all the others. The minimum k-way cut problem is known as NP-hard even if all vertex degrees are three or less and k is equal to 3. The minimum k-way cut problem for a planar graph and fixed integer k can be solved in polynomial time. This paper presents an algorithm for computing a minimum three-way cut of a graph in a larger class than planar graphs.>

In this paper, we propose a heuristic floorplanning method. It is based on tentative insertion of constraints, that intentionally produces redundant constraints to make it possible to search in a wide range of solution space. The proposed method reduces the total area of blocks with the removal and insertion of constraints on the critical path in both horizontal and vertical constraint graphs. Experimental results showed that the quality of solutions of the proposed method is good and even for the large number of blocks, the proposed method keeps a high quality of solution.>

The graph partitioning problem is to partition the vertices of an undirected graph G=(V, E) into two sets of equal size such that the number of edges between them is minimized. In this paper, we propose a systolic algorithm for graph partitioning. The algorithm is based on the Kernighan-Lin heuristic algorithm, runs on a linear array consisting of O(|V|) processing units, and is very suitable for direct VLSI implementation. Computation time of one pass of the proposed algorithm is O(|V|). Simulation experiments showed that the proposed algorithm is as good as the original KL heuristic.>