Forty Thieves is a solitaire game with two 52-card decks. The object is to move all cards from ten tableau piles of four cards to eight foundations. Each foundation is built up by suit from ace to king of the same suit, and each tableau pile is built down by suit. You may move the top card from any tableau pile to a tableau or foundation pile, and from the stock to a foundation pile. We prove that the generalized version of Forty Thieves is NP-complete.

In this paper, we modify the Legendre-Sidelnikov sequence which was defined by M. Su and A. Winterhof and consider its exact autocorrelation values. This new sequence is balanced for any p,q and proved to possess low autocorrelation values in most cases.

This paper presents a synchronization mechanism to effectively implement the lock and barrier protocols in a decentralized manner through explicit message passing. In the proposed solution, a simple and efficient synchronization control mechanism is proposed to support queued synchronization without contention. By using state-of-the-art Application-Specific Instruction-set Processor (ASIP) technology, we embed the synchronization functionality into a baseline processor, making the proposed mechanism feature ultra-low overhead. Experimental results show the proposed synchronization achieves ultra-low latency and almost ideal scalability when the number of processors increases.

So far, many approaches for detecting code clones have been proposed based on the different degrees of normalizations (e.g. removal of white spaces, tokenization, and regularization of identifiers). Different degrees of normalizations lead to different granularities of source code to be detect as code clones. To investigate how the normalizations impact the code clone detection, this study proposes six approaches for detecting code clones with preprocessing input source files using different degrees of normalizations. More precisely, each normalization is applied to the input source files and then equivalence class partitioning is performed to the files in the preprocessing. After that, code clones are detected from a set of files that are representatives of each equivalence class using a token-based code clone detection tool named CCFinder. The proposed approaches can be categorized into two types, approaches with non-normalization and normalization. The former is the detection of only identical files without any normalization. Meanwhile, the latter category is the detection of identical files with different degrees of normalizations such as removal of all lines containing macros. From the case study, we observed that our proposed approaches detect code clones faster than the approach that uses only CCFinder. We also found the approach with non-normalization is the fastest among the proposed approaches in many cases.

In Recent years, a paradigm of optimization algorithms referred to as “meta-heuristics” have been gaining attention as a means of obtaining approximate solutions to optimization problems quickly without any special prior knowledge of the problems. Meta-heuristics are characterized by flexibility in implementation. In practical applications, we can make use of not only existing algorithms but also revised algorithms that reflect the prior knowledge of the problems. Most meta-heuristic algorithms lack mathematical grounds, however, and therefore generally require a process of trial and error for the algorithm design and its parameter adjustment. For one of the resolution of the problem, we propose an approach to design algorithms with mathematical grounds. The approach consists of first constructing a “framework” of which dynamic characteristics can be derived theoretically and then designing concrete algorithms within the framework. In this paper, we propose such a framework that employs two following basic strategies commonly used in existing meta-heuristic algorithms, namely, (1) multipoint searching, and (2) stochastic searching with pseudo-random numbers. In the framework, the update-formula of search point positions is given by a linear combination of normally distributed random numbers and a fixed input term. We also present a stability theory of the search point distribution for the proposed framework, using the variance of the search point positions as the index of stability. This theory can be applied to any algorithm that is designed within the proposed framework, and the results can be used to obtain a control rule for the search point distribution of each algorithm. We also verify the stability theory and the optimization capability of an algorithm based on the proposed framework by numerical simulation.

In this work, the differential received signal strength based localization problem is addressed. Based on the measurement model, we present the constrained weighted least squares (CWLS) approach, which is difficult to be solved directly due to its nonconvex nature. However, by performing the semidefinite relaxation (SDR) technique, the CWLS problem can be relaxed into a semidefinite programming problem (SDP), which can be efficiently solved using modern convex optimization algorithms. Moreover, the SDR is proved to be tight, and hence ensures the corresponding SDP find the optimal solution of the original CWLS problem. Numerical simulations are included to corroborate the theoretical results and promising performance.

This paper seeks to improve power-performance efficiency of embedded systems by the use of dynamic reconfiguration. Programmable logic devices (PLDs) have the competence to optimize the power consumption by the use of partial and/or dynamic reconfiguration. It is a non-exclusive approach, which can use other power-reduction techniques simultaneous, and thus it is applicable to a myriad of systems. The power-performance improvement by dynamic reconfiguration was evaluated through an augmented reality system that translates Japanese into English. It is a wearable and mobile system with a head-mounted display (HMD). In the system, the computing core detects a Japanese word from an input video frame and the translated term will be output to the HMD. It includes various image processing approaches such as pattern recognition and object tracking, and these functions run sequentially. The system does not need to prepare all functions simultaneously, which provides a function by reconfiguration only when it is needed. In other words, by dynamic reconfiguration, the spatiotemporal module-based pipeline can introduce the reduction of its circuit amount and power consumption compared to the naive approach. The approach achieved marked improvements; the computational speed was the same but the power consumption was reduced to around $rac{1}{6}$.

The success of heuristic search in AI planning largely depends on the design of the heuristic. On the other hand, previous experience contains potential domain information that can assist the planning process. In this context, we have studied dynamic macro-based heuristic planning through action relationship analysis. We present an approach for analyzing the action relationship and design an algorithm that learns macros in solved cases. We then propose a dynamic macro-based heuristic that appropriately reuses the macros rather than immediately assigning them to domains. The above ideas are incorporated into a working planning system called Dynamic Macro-based Fast Forward planner. Finally, we evaluate our method in a series of experiments. Our method effectively optimizes planning since it reduces the result length by an average of 10% relative to the FF, in a time-economic manner. The efficiency is especially improved when invoking an action consumes time.

In this paper, we discuss performance modeling of 3-D stencil computing on an FPGA accelerator with a high-level synthesis environment, aiming for efficient exploration of user-space design parameters. First, we analyze resource utilization and performance to formulate these relationships as mathematical models. Then, in order to evaluate our proposed models, we implement heat conduction simulations as a benchmark application, by using MaxCompiler, which is a high-level synthesis tool for FPGAs, and MaxGenFD, which is a domain specific framework of the MaxCompiler for finite-difference equation solvers. The experimental results with various settings of architectural design parameters show the best combination of design parameters for pipeline structure can be systematically found by using our models. The effects of changing arithmetic accuracy and using data stream compression are also discussed.

Video Up-scaling is a hotspot in TV display area; as an important brunch of Video Up-scaling, Texture-Based Video Up-scaling (TBVU) method shows great potential of hardware implementation. Coarse-grained Reconfigurable Architecture (CGRA) is a very promising processor; it is a parallel computing platform which provides high performance of hardware, high flexibility of software, and dynamical reconfiguration ability. In this paper we propose an implementation of TBVU on CGRA. We fully exploit the characters of TBVU and utilize several techniques to reduce memory I/O operation and total execution time. Experimental results show that our work can greatly reduce the I/O operation and the execution time compared with the non-optimized ones. We also compare our work with other platforms and find great advantage in execution time and resource utilization rate.

A serial ATA PHY fabricated in a 0.15-µm CMOS process performs the serial ATA operation in an asynchronous transition by using large variation in the reference clock. This technique calibrates a transmission signal frequency by utilizing the received signal. This is achieved by calibrating the divide ratio of a spread-spectrum clock generator (SSCG). This technique enables a serial ATA PHY to use reference oscillators with a production-frequency tolerance of less than 400ppm, i.e., higher than the permissible TX frequency variations (i.e., 350ppm). The calibrated transmission signal achieved a total jitter of 3.9ps.

Social recommendation systems that make use of the user's social information have recently attracted considerable attention. These recommendation approaches partly solve cold-start and data sparsity problems and significantly improve the performance of recommendation systems. The essence of social recommendation methods is to utilize the user's explicit social connections to improve recommendation results. However, this information is not always available in real-world recommender systems. In this paper, a solution to this problem of explicit social information unavailability is proposed. The existing user-item rating matrix is used to compute implicit social information, and then an ISRec (implicit social recommendation algorithm) which integrates this implicit social information and the user-item rating matrix for social recommendation is introduced. Experimental results show that our method performs much better than state-of-the-art approaches; moreover, complexity analysis indicates that our approach can be applied to very large datasets because it scales linearly with respect to the number of observations in the matrices.

We proposed a hard-wired CPG hardware network to reproduce the gaits of four-legged animals. It should reproduce walking and bounding, and they should be switchable with each other by changing the value of only one voltage.

Providing images captured by an on-board camera to surrounding vehicles is an effective method to achieve smooth road traffic and to avoid traffic accidents. We consider providing images using WiFi technology based on the IEEE802.11p standard for vehicle-to-vehicle (V2V) communication media. We want to compress images to suppress communication traffic, because the communication capacity of the V2V system is strictly limited. However, there are difficulties in image compression and transmission using wireless communication especially in a vehicular broadcast environment, due to transmission errors caused by fading, packet collision, etc. In this letter, we propose an image transmission technique based on compressed sensing. Through computer simulations, we show that our proposed technique can achieve stable image reconstruction despite frequent packet error.

For low-density parity-check codes, spatial coupling was proved to boost the performance of iterative decoding up to the optimal performance. As an application of spatial coupling, in this paper, bit-interleaved coded modulation (BICM) with spatially coupled (SC) interleaving — called SC-BICM — is considered to improve the performance of iterative channel estimation and decoding for block-fading channels. In the iterative receiver, feedback from the soft-in soft-out decoder is utilized to refine the initial channel estimates in linear minimum mean-squared error (LMMSE) channel estimation. Density evolution in the infinite-code-length limit implies that the SC-BICM allows the receiver to attain accurate channel estimates even when the pilot overhead for training is negligibly small. Furthermore, numerical simulations show that the SC-BICM can provide a steeper reduction in bit error rate than conventional BICM, as well as a significant improvement in the so-called waterfall performance for high rate systems.

In the era of IPv6, since the number of IPv6 addresses rapidly increases and the required speed is more than Giga lookups per second (GLPS), an area-efficient and high-speed IP lookup architecture is desired. This paper shows a parallel index generation unit (IGU) for memory-based IPv6 lookup architecture. To reduce the size of memory in the IGU, we use a linear transformation and a row-shift decomposition. A single-memory realization requires O(2l log k) memory size, where l denotes the length of prefix, while the realization using IGU requires O(kl) memory size, where k denotes the number of prefixes. In IPv6 prefix lookup, since l is at most 64 and k is about 340 K, the IGU drastically reduces the memory size. Also, to reduce the cost, we realize the parallel IGU by using both on-chip and off-chip memories. We show a design algorithm for the parallel IGU to store given off-chip and on-chip memories. The parallel IGU has a simple architecture and performs lookup by using complete pipelines those insert the pipeline registers in all the paths. We loaded more than 340 K IPv6 pseudo prefixes on the Xilinx Virtex 6 FPGA with off-chip DDRII+ Static RAMs (SRAMs). Its lookup speed is 1.100 giga lookups per second (GLPS) which is sufficient for the required speed for a next generation 400 Gbps link throughput. As for the normalized area and lookup speed, our implementation outperforms existing FPGA implementations.

A processing system with multiple field programmable gate array (FPGA) cards is described. Each FPGA card can interconnect using six I/O (up, down, left, right, front, and back) terminals. The communication network among FPGAs is scalable according to user design. When the system operates multi-dimensional applications, transmission efficiency among FPGA improved through user-adjusted dimensionality and network topologies for different applications. We provide a fast and flexible circuit configuration method for FPGAs of a multi-dimensional FPGA array. To demonstrate the effectiveness of the proposed method, we assess performance and power consumption of a circuit that calculated 3D Poisson equations using the finite difference method.

We present an algorithm for efficient rendering of animated hair under a dynamic, low-frequency lighting environment. We use spherical harmonics (SH) to represent the environmental light. The transmittances between a point on a hair strand and the light sources are also represented by SH functions. Then, a convolution of SH functions and the scattering function of a hair strand is precomputed. This allows us to efficiently compute the intensity at a point on the hair. However, the computation of the transmittance is very time-consuming. We address this problem by using a voxel-based approach: the transmittance is computed by using a voxelized hair model. We further accelerate the computation by sampling the voxels. By using our method, we can render a hair model consisting of tens of thousands of hair strands at interactive frame rates.

In this letter, we propose a low complexity fixed sphere decoder (FSD) with statistical threshold for multiple-input and multiple-output (MIMO) systems. The proposed algorithm is developed by applying two threshold-based pruning algorithms using an initial detection and statistical noise constraint to the FSD. The proposed FSD algorithm is suitable for a fully pipelined hardware implementation and also has low complexity because the threshold of the proposed pruning algorithm is pre-calculated and independently applied to the path without sorting operation. Simulation results show that the proposed FSD has the performance of the original FSD as well as a low complexity compared to the original FSD and other low complexity FSD algorithms.

As one of optical wireless Orthogonal Frequency Division Multiplexing (OFDM) systems, there is Flip-OFDM, which separates an OFDM signal into positive and negative parts and transmits them. It has good power efficiency and low hardware complexity. However, the system halves transmission efficiency compared with Direct Current-biased Optical OFDM. In this paper, Circular Polarized Optical OFDM (CPO-OFDM) is presented. This system separates OFDM signals into positive and negative parts, and it converts these signals into left-handed and right-handed polarization, and it multiplexes these signals. CPO-OFDM is analyzed with an intensity modulation/direct detection channel model which considers the change of the state of polarization owing to free space propagation. As a result of the analysis, it is shown that CPO-OFDM is a flexible system like the conventional systems by using circular polarization and it has the equivalent bit error rate (BER) and the double transmission efficiency compared with Flip-OFDM. The IM/DD channel model which considers the degree of polarization (DOP) is also shown. As for the DOP, it improves by the increase of the propagation distance. Thus, we can achieve the equivalent BER obtained with a high DOP laser even if we use a low DOP laser.