In this note we suggest a new parallelizable mode of operation for message authentication codes (MACs). The new MAC algorithm iterates a pseudo-random function (PRF) FK:{0,1}m → {0,1}n, where K is a key and m,n are positive integers such that m ≥ 2n. The new construction is an improvement over a sequential MAC algorithm presented at FSE2008, solving positively an open problem posed in the paper – the new mode is capable of fully parallel execution while achieving rate-1 efficiency and “full n-bit” security. Interestingly enough, PMAC-like parallel structure, rather than CBC-like serial iteration, has beneficial side effects on security. That is, the new construction is provided with a more straightforward security proof and with an even better (“-free”) security bound than the FSE 2008 construction.

Context awareness is one of the ultimate goals of ubiquitous computing, and spatial information plays an important role in building context awareness. In this paper, we propose a new interoperable spatial information model, which is based on ucode relation (ucR) and Place Identifier (PI), for realizing ubiquitous spatial infrastructure. In addition, we propose a design environment for spatial information database using our model. Our model is based on ucode and its relation. ucode is 128 bits number and the number itself has no meaning. Hence, it is difficult to manage the relation between ucodes without using a tool. Our design environment provides to describe connection between each ucode visually and is able to manipulate data using the target space map interactively. To evaluate the proposed model and environment, we designed three spaces using our tool. In addition, we developed a web application using our spatial model. From evaluation, we have been showed that our model is effective and our design environment is useful to develop our spatial information model.

A construction of shift sequence sets is proposed. Multiple distinct shift sequence sets are obtained by changing the parameters of the shift sequences. The shift sequences satisfy the conditions that P|L and P ≥ 2, where P is the length of the shift sequences, L is the length of the zero-correlation zone or low-correlation zone (ZCZ/LCZ). Then based on these shift sequence sets, many shift distinct ZCZ/LCZ sequence sets are constructed by using interleaving technique and complex Hadamard matrices. Furthermore, the new construction is optimal under the conditions proposed in this paper. Compared with previous constructions, the proposed construction extends the number of shift distinct ZCZ/LCZ sequence sets, so that more sequence sets are obtained for multi-cell quasi-synchronous code-division multiple access (QS-CDMA) systems.

Recent idea visualization programs still lack automatic idea summarization capabilities. This paper presents a knowledge-based method for automatically providing a short piece of English text about a topic to each idea group in idea charts. This automatic topic identification makes used Yet Another General Ontology (YAGO) and Wordnet as its knowledge bases. We propose a novel topic selection method and we compared its performance with three existing methods using two experimental datasets constructed using two idea visualization programs, i.e., the KJ Method (Kawakita Jiro Method) and mind-mapping programs. Our proposed topic identification method outperformed the baseline method in terms of both performance and consistency.

NTRU is a public key cryptosystem based on hard problems over lattices. In this paper, we present efficient methods for convolution product computation which is a dominant operation of NTRU. The new methods are based on the observation that repeating patterns in coefficients of an NTRU polynomial can be used for the construction of look-up tables, which is a similar approach to the sliding window methods for exponentiation. We provide efficient convolution algorithms to implement this idea, and we make a comprehensive analysis of the complexity of the new algorithms. We also give software implementations over a Pentium IV CPU, a MICAz mote, and a CUDA-based GPGPU platform. According to our analyses and experimental results, the new algorithms speed up the NTRU encryption and decryption operations by up to 41%.

The multivariate public key cryptosystem (MPKC), which is based on the problem of solving a set of multivariate systems of quadratic equations over a finite field, is expected to be secure against quantum attacks. Although there are several existing schemes in MPKC that survived known attacks and are much faster than RSA and ECC, there have been few discussions on security against physical attacks, aside from the work of Okeya et al. (2005) on side-channel attacks against Sflash. In this study, we describe general fault attacks on MPKCs including Big Field type (e.g. Matsumoto-Imai, HFE and Sflash) and Stepwise Triangular System (STS) type (e.g. UOV, Rainbow and TTM/TTS). For both types, recovering (parts of) the secret keys S,T with our fault attacks becomes more efficient than doing without them. Especially, on the Big Field type, only single fault is sufficient to recover the secret keys.

In this paper, we study decentralized supervisory control of timed discrete event systems, where we adopt the OR rule for fusing local enablement decisions and the AND rule for fusing local enforcement decisions. Under these rules, necessary and sufficient conditions for the existence of a decentralized supervisor that achieves a given specification language are easily obtained from the result of literature. If a given specification language does not satisfy these existence conditions, we must compute its sublanguage satisfying them. The main contribution of this paper is proposing a method for computing such a sublanguage.

The present paper introduces a prototype design and experimental results for a multi-user MIMO linear precoding system. A base station and two mobile stations are implemented by taking full advantage of the software-defined radio. The base station consists of general purpose signal analyzers and signal generators controlled by a personal computer. Universal software radio peripherals are used as mobile stations. Linear spatial precoding and a simple two-way channel estimation technique are adopted in this experimental system. In-lab and field transmission experiments are carried out, and the bit error rate performance is evaluated. The impact of the channel estimation error under average channel gain discrepancy between two mobile stations is analyzed through computer simulations. Channel estimation error is shown to have a greater influence on the mobile station with the greater average channel gain.

This paper presents a blocked united algorithm for the all-pairs shortest paths (APSP) problem. This algorithm simultaneously computes both the shortest-path distance matrix and the shortest-path construction matrix for a graph. It is designed for a high-speed APSP solution on hybrid CPU-GPU systems. In our implementation, two most compute intensive parts of the algorithm are performed on the GPU. The first part is to solve the APSP sub-problem for a block of sub-matrices, and the other part is a matrix-matrix “multiplication” for the APSP problem. Moreover, the amount of data communication between CPU (host) memory and GPU memory is reduced by reusing blocks once sent to the GPU. When a problem size (the number of vertices in a graph) is large enough compared to a block size, our implementation of the blocked algorithm requires CPU GPU exchanging of three blocks during a block computation on the GPU. We measured the performance of the algorithm implementation on two different CPU-GPU systems. A system containing an Intel Sandy Bridge CPU (Core i7 2600K) and an AMD Cayman GPU (Radeon HD 6970) achieves the performance up to 1.1 TFlop/s in a single precision.

In this work, a simple doped accumulator (DACC)-assisted relay system is proposed by using bit-interleaved coded modulation with iterative decoding (BICM-ID). An extrinsic information transfer (EXIT) chart analysis shows that DACC keeps the convergence tunnel of the EXIT curves open until almost the (1, 1) point of the mutual information, which avoids the error floor. In the relay system, errors may happen in the source-relay link (intra-link), however, they are allowed in our proposed technique where the correlation knowledge between the source and the relay is exploited at the destination node. Strong codes are not needed and even the systematic source bits can be simply extracted at the relay even though the systematic part may contain some errors. Hence, the complexity of the relay can be significantly reduced, and thereby the proposed system is energy-efficient. Furthermore, the error probability of the intra-link can be estimated at the receiver by utilizing the a posteriori log-likelihood ratios (LLRs) of the two decoders, and it can be further utilized in the iterative processing. Additionally, we provide the analysis of different relay location scenarios and compare the system performances by changing the relay's location. The transmission channels in this paper are assumed to suffer from additive white Gaussian noise (AWGN) and block Rayleigh fading. The theoretical background of this technique is the Slepian-Wolf/Shannon theorem for correlated source coding. The simulation results show that the bit-error-rate (BER) performances of the proposed system are very close to theoretical limits supported by the Slepian-Wolf/Shannon theorem.

Multicore processor architectures have become ubiquitous in today's computing platforms, especially in parallel computing installations, with their power and cost advantages. While the technology trend continues towards having hundreds of cores on a chip in the foreseeable future, an urgent question posed to system designers as well as application users is whether applications can receive sufficient support on today's operating systems for them to scale to many cores. To this end, people need to understand the strengths and weaknesses on their support on scalability and to identify major bottlenecks limiting the scalability, if any. As open-source operating systems are of particular interests in the research and industry communities, in this paper we choose three operating systems (Linux, Solaris and FreeBSD) to systematically evaluate and compare their scalability by using a set of highly-focused microbenchmarks for broad and detailed understanding their scalability on an AMD 32-core system. We use system profiling tools and analyze kernel source codes to find out the root cause of each observed scalability bottleneck. Our results reveal that there is no single operating system among the three standing out on all system aspects, though some system(s) can prevail on some of the system aspects. For example, Linux outperforms Solaris and FreeBSD significantly for file-descriptor- and process-intensive operations. For applications with intensive sockets creation and deletion operations, Solaris leads FreeBSD, which scales better than Linux. With the help of performance tools and source code instrumentation and analysis, we find that synchronization primitives protecting shared data structures in the kernels are the major bottleneck limiting system scalability.

In this paper, we propose a virtualization architecture for a multi-core embedded system to provide more system reliability and security while maintaining performance and without introducing additional special hardware supports or implementing a complex protection mechanism in the virtualization layer. Embedded systems, especially consumer electronics, have often used virtualization. Virtualization is not a new technique, as there are various uses for both GPOS (General Purpose Operating System) and RTOS (Real Time Operating System). The surge of the multi-core platforms in embedded systems also helps consolidate the virtualization system for better performance and lower power consumption. Embedded virtualization design usually uses two approaches. The first is to use the traditional VMM, but it is too complicated for use in the embedded environment without additional special hardware support. The other approach uses the microkernel, which imposes a modular design. The guest systems, however, would suffer from considerable modifications in this approach, as the microkernel allows guest systems to run in the user space. For some RTOSes and their applications originally running in the kernel space, this second approach is more difficult to use because those codes use many privileged instructions. To achieve better reliability and keep the virtualization layer design lightweight, this work uses a common hardware component adopted in multi-core embedded processors. In most embedded platforms, vendors provide additional on-chip local memory for each physical core, and these local memory areas are only private to their cores. By taking advantage of this memory architecture, we can mitigate the above-mentioned problems at once. We choose to re-map the virtualization layer's program on the local memory, called SPUMONE, which runs all guest systems in the kernel space. Doing so, it can provide additional reliability and security for the entire system because the SPUMONE design in a multi-core platform has each instance installed on a separate processor core. This design differs from traditional virtualization layer design, and the content of each SPUMONE is inaccessible to the others. We also achieve this goal without adding overhead to the overall performance.

With the trend towards increasing number of cores, for example, 1000 cores, interconnection network in manycore chips has become the critical bottleneck for providing communication infrastructures among on-chip cores as well as to off-chip memory. However, conventional on-chip mesh topologies do not scale up well because remote cores are generally separated by too many hops due to the small-radix routers within these networks. Moreover, projected scaling of electrical processor-memory network appears unlikely to meet the enormous demand for memory bandwidth while satisfying stringent power budget. Fortunately, recent advances in 3D integration technology and silicon photonics have provided potential solutions to these challenges. In this paper, we propose a hybrid photonic burst-switched interconnection network for large-scale manycore processors. We embed an electric low-diameter flattened butterfly into 3D stacking layers using integer linear programming, which results in a scalable low-latency network for inter-core packets exchange. Furthermore, we use photonic burst switching (PBS) for processor-memory network. PBS is an adaptation of optical burst switching for chip-scale communication, which can significantly improve the power efficiency by leveraging sub-wavelength, bandwidth-efficient optical switching. Using our physically-accurate network-level simulation environment, we examined the system feasibility and performances. Simulation results show that our hybrid network achieves up to 25% of network latency reduction and up to 6 times energy savings, compared to conventional on-chip mesh network and optical circuit-switched memory access scheme.

The Boolean network (BN) can be used to create discrete mathematical models of gene regulatory networks. In this paper, we consider three problems on BNs that are known to be NP-hard: detection of a singleton attractor, finding a control strategy that shifts a BN from a given initial state to the desired state, and control of attractors. We propose integer programming-based methods which solve these problems in a unified manner. Then, we present results of computational experiments which suggest that the proposed methods are useful for solving moderate size instances of these problems. We also show that control of attractors is -hard, which suggests that control of attractors is harder than the other two problems.

System-on-display panel design methodologies are proposed with the purpose of integrating DCT and IDCT on display panels for image codec and peripheral systems so as to reduce the bus data rate, memory size and power consumption. Unified constant geometry algorithms and architectures including recursive additions are proposed for DCT and IDCT butterfly computation, recursive additions and interconnections between stages. These schemes facilitate VLSI implementation and improve fault tolerance, suitable for low-yield SOP processing technologies through duplicate use of a PE as all the butterfly and recursive addition stages are composed and interconnected in a regular fashion. Efficient redundancy replacement methodologies optimizing the computation speed and the amount of hardware in various application areas are also described with testability and reliability issues. Finally, a performance analysis of speed, hardware and interconnection complexity is described with the proposed work's advantages.

In this paper we report on an approach inspired by Ant Colony Optimization (ACO) to provide a fault tolerant and efficient means of transferring data in dynamic environments. We investigate the problem of distributing data between a client and server by using pheromone equations. Ants choose the best source of food by selecting the strongest pheromone trail leaving the nest. The pheromone decays over-time and needs to be continually reinforced to define the optimum route in a dynamic environment. This resembles the dynamic environment for the distribution of data between clients and servers. Our approach uses readily available network and server information to construct a pheromone that determines the best server from which to download data. We demonstrate that the approach is self-optimizing and capable of adapting to dynamic changes in the environment.

In this paper, we have addressed the problem of ordering transactions in network-on-chips (NoCs) for post-silicon validation. The main idea is to extract the order of the transactions from the local partial orders in each NoC tile based on a set of “happened-before” rules, assuming transactions do not have a timestamp. The assumption is based on the fact that implementation and usage of a global time as timestamp in such systems may not be practical or efficient. When a new transaction is received in a tile, we send special messages to the neighboring tiles to inform them regarding the new transaction. The process of sending those special messages continues recursively in all the tiles that receive them until another such special message is detected. This way, we relate local orders of different tiles with each other. We show that our method can reconstruct the correct transaction orders when communication delays are deterministic. We have shown the effectiveness of our method by correctly ordering the transaction in NoCs with mesh and torus topologies with different sizes from 5*5 to 9*9. Also, we have implemented the proposed method in hardware to show its feasibility.

The interference rejection combining (IRC) receiver, which can suppress inter-cell interference, is effective in improving the cell-edge user throughput. The IRC receiver is typically based on the minimum mean square error (MMSE) criteria, and requires a covariance matrix including the interference signals, in addition to a channel matrix from the serving cell. Therefore, in order to clarify the gain from the IRC receiver, the actual estimation error of these matrices should be taken into account. In a system performance evaluation, the link performance modeling of the IRC receiver, i.e., the output signal-to-interference-plus-noise power ratio (SINR) after IRC reception including the estimation errors, is very important in evaluating the actual performance of the IRC receiver in system level simulations. This is because these errors affect the suppression of the interference signals for the IRC receiver. Therefore, this paper investigates and proposes IRC receiver modeling schemes for the covariance matrix and channel estimation errors. As the modeling scheme for the covariance matrix, we propose a scheme that averages the conventional approximation using the complex Wishart distribution in the frequency domain to address issues that arise in a frequency selective fading channel. Furthermore, we propose a modeling scheme for the channel estimation error according to the ideal channel response of all cells and a channel estimation filter to address channel fading fluctuations. The results of simulations assuming the LTE/LTE-Advanced downlink with two transmitter and receiver antenna branches show that the proposed modeling scheme for the covariance matrix estimation error accurately approximates the performance of a realistic IRC receiver, which estimates the covariance matrix and channel matrix of the serving cell based on the demodulation reference signal (DM-RS), even in a frequency selective fading channel. The results also show that the proposed modeling scheme for the channel estimation error is a robust scheme in terms of the r.m.s. delay spread of a channel model compared to the scheme using the mean square error (MSE) statistic of the estimated channel coefficients based on a channel estimation filter.

Software FMEA is valuable and practically used for embedded software of safety-critical systems. In this paper, a novel method for Software FMEA is presented based on co-analysis of system model and software model. The method is hopeful to detect quantitative and dynamic effects by a targeted software failure. A typical application of the method is provided to illustrate the procedure and the applicable scenarios. In addition, a pattern is refined from the application for further reuse.

This paper introduces novel high-speed and low-power boosted level converters for use in dual-supply systems. The proposed level converters adopt a voltage boosting at the gate of pull-down transistors to improve driving speed and reduce contention problem. Comparison results in a 0.13-µm CMOS process indicated that the proposed level converters provided up to 70% delay reduction with up to 57% power-delay product (PDP) reduction as compared to conventional level converters.