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 analyzes complexities of decision diagrams for elementary functions such as polynomial, trigonometric, logarithmic, square root, and reciprocal functions. These real functions are converted into integer-valued functions by using fixed-point representation. This paper presents the numbers of nodes in decision diagrams representing the integer-valued functions. First, complexities of decision diagrams for polynomial functions are analyzed, since elementary functions can be approximated by polynomial functions. A theoretical analysis shows that binary moment diagrams (BMDs) have low complexity for polynomial functions. Second, this paper analyzes complexity of edge-valued binary decision diagrams (EVBDDs) for monotone functions, since many common elementary functions are monotone. It introduces a new class of integer functions, Mp-monotone increasing function, and derives an upper bound on the number of nodes in an EVBDD for the Mp-monotone increasing function. A theoretical analysis shows that EVBDDs have low complexity for Mp-monotone increasing functions. This paper also presents the exact number of nodes in the smallest EVBDD for the n-bit multiplier function, and a variable order for the smallest EVBDD.

This paper proposes a design method and programmable architectures for numerical function generators (NFGs) of two-variable functions. To realize a two-variable function in hardware, we partition a given domain of the given function into segments, and approximate the function by a polynomial in each segment. This paper introduces two planar segmentation algorithms that efficiently partition a domain of a two-variable function. This paper also introduces two architectures that can realize a wide range of two-variable functions. Our architectures allow a systematic design of two-variable functions. FPGA implementation results show that, for a complicated function, our NFG achieves 58% of memory size and 39% of delay time of a circuit designed using one-variable NFGs.

Two-variable numerical functions are widely used in various applications, such as computer graphics and digital signal processing. Fast and compact hardware implementations are required. This paper introduces the bilinear interpolation method to produce fast and compact numerical function generators (NFGs) for two-variable functions. This paper also introduces a design method for symmetric two-variable functions. This method can reduce the memory size needed for symmetric functions by nearly half with small speed penalty. Experimental results show that the bilinear interpolation method can significantly reduce the memory size needed for two-variable functions, and the speed of NFGs based on the bilinear method is comparable to that of NFGs based on tangent plane approximation. For a complicated function, our NFG is faster and more compact than a circuit designed using a one-variable NFG.

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 introduce the edge-valued binary decision diagram (EVBDD) to reduce the memory and delay in numerical function generators (NFGs). An NFG realizes a function, such as a trigonometric, logarithmic, square root, or reciprocal function, in hardware. NFGs are important in, for example, digital signal applications, where high speed and accuracy are necessary. We use the EVBDD to produce a fast and compact segment index encoder (SIE) that is a key component in our NFG. We compare our approach with NFG designs based on multi-terminal BDDs (MTBDDs), and show that the EVBDD produces SIEs that have, on average, only 7% of the memory and 40% of the delay of those designed using MTBDDs. Therefore, our NFGs based on EVBDDs have, on average, only 38% of the memory and 59% of the delay of NFGs based on MTBDDs.

This paper focuses on numerical function generators (NFGs) based on k-th order polynomial approximations. We show that increasing the polynomial order k reduces significantly the NFG's memory size. However, larger k requires more logic elements and multipliers. To quantify this tradeoff, we introduce the FPGA utilization measure, and then determine the optimum polynomial order k. Experimental results show that: 1) for low accuracies (up to 17 bits), 1st order polynomial approximations produce the most efficient implementations; and 2) for higher accuracies (18 to 24 bits), 2nd-order polynomial approximations produce the most efficient implementations.

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 the algorithm that combine RM QRM-MLD algorithm we proposed and independent adaptive control of surviving symbol replica candidates (we call this technique IAC) using Manhattan metric as method of metric calculation, and evaluate the BER performance and computational complexity of this algorithm. Combining RM QRM-MLD and IAC, within a high Eb/No range, the BER performance of the algorithm degrade because of excess reduction of surviving symbol replica candidates at each stage. Thus, in this case, there is a proper value of the parameter X for each Eb/No value. We investigate the value and simulate the BER performance and computational complexity in the case of application of the proper value.

This paper proposes an architecture and a synthesis method for high-speed computation of fixed-point numerical functions such as trigonometric, logarithmic, sigmoidal, square root, and combinations of these functions. Our architecture is based on the lookup table (LUT) cascade, which results in a significant reduction in circuit complexity compared to traditional approaches. This is suitable for automatic synthesis and we show a synthesis method that converts a Matlab-like specification into an LUT cascade design. Experimental results show the efficiency of our approach as implemented on a field-programmable gate array (FPGA)

This paper presents architecture and a synthesis method for programmable numerical function generators (NFGs) for trigonometric, logarithmic, square root, and reciprocal functions. Our NFG partitions a given domain of the function into nonuniform segments using a LUT cascade, and approximates the given function by a quadratic polynomial for each segment. Thus, we can implement fast and compact NFGs for a wide range of functions. Implementation results on an FPGA show that: 1) our NFGs require only 4% of the memory needed by NFGs based on the linear approximation with nonuniform segmentation; and 2) our NFGs require only 22% of the memory needed by NFGs based on the 5th-order approximation with uniform segmentation. Our automatic synthesis system generates such compact NFGs quickly.

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

This paper proposes symbol replica candidates reduction type QRM-MLD using simple quadrant detection for 4-by-4 MIMO/SDM system with 16 QAM. Though MLD is known as the optimal SDM signal detection algorithm, its computational complexity is exponential in the number of transmit antennas (van Zeltst et al). As the signal detection algorithm that can greatly decrease its computational complexity, QRM-MLD with adaptive selection of surviving symbol replica candidates is proposed (Higuchi et al.). While this algorithm is using multiple quadrant detections and symbol ranking, we propose a simple algorithm in terms of operation though the number of calculation of branch metrics is larger than that of its algorithm. In this paper, we compare the BER performance and computational complexity of the proposed scheme with that of conventional QRM-MLD and MLD.

This paper presents an architecture and a synthesis method for programmable numerical function generators of trigonometric functions, logarithm functions, square root, reciprocal, etc. Our architecture uses an LUT (look-up table) cascade as the segment index encoder, compactly realizes various numerical functions, and is suitable for automatic synthesis. We have developed a synthesis system that converts MATLAB-like specification into HDL code. We propose and compare three architectures implemented as a FPGA (field-programmable gate array). Experimental results show the efficiency of our architecture and synthesis system.

This paper proposes minimization algorithms for the memory size and the average path length (APL) of heterogeneous multivalued decision diagrams (MDDs). In a heterogeneous MDD, each multivalued variable can take different domains. To represent a binary logic function using a heterogeneous MDD, we partition the binary variables into groups with different numbers of binary variables and treat the groups as multivalued variables. Since memory size and APL of a heterogeneous MDD depend on the partition of binary variables as well as the ordering of binary variables, the memory size and the APL of a heterogeneous MDD can be minimized by considering both orderings and partitions of binary variables. The experimental results show that heterogeneous MDDs can represent logic functions with smaller memory sizes than free binary decision diagrams (FBDDs) and smaller APLs than reduced ordered BDDs (ROBDDs); the APLs of heterogeneous MDDs can be reduced by half of the ROBDDs without increasing memory size; and heterogeneous MDDs have smaller area-time complexities than MDD(k)s.