Mobile edge computing (MEC) is a new computing paradigm, which provides computing support for resource-constrained user equipments (UEs). In this letter, we design an effective incentive framework to encourage MEC operators to provide computing service for UEs. The problem of jointly allocating communication and computing resources to maximize the revenue of MEC operators is studied. Based on auction theory, we design a multi-round iterative auction (MRIA) algorithm to solve the problem. Extensive simulations have been conducted to evaluate the performance of the proposed algorithm and it is shown that the proposed algorithm can significantly improve the overall revenue of MEC operators.
Tarek SAADAWI Akira KAWAGUCHI Myung Jong LEE Abbe MOWSHOWITZ
Systems for Internet of Things (IoT) have generated new requirements in all aspects of their development and deployment, including expanded Quality of Service (QoS) needs, enhanced resiliency of computing and connectivity, and the scalability to support massive numbers of end devices in a variety of applications. The research reported here concerns the development of a reliable and secure IoT/cyber physical system (CPS), providing network support for smart and connected communities, to be realized by means of distributed, secure, resilient Edge Cloud (EC) computing. This distributed EC system will be a network of geographically distributed EC nodes, brokering between end-devices and Backend Cloud (BC) servers. This paper focuses on three main aspects of the CPS: a) resource management in mobile cloud computing; b) information management in dynamic distributed databases; and c) biological-inspired intrusion detection system.
Picross 3D is a popular single-player puzzle video game for the Nintendo DS. It presents a rectangular parallelepiped (i.e., rectangular box) made of unit cubes, some of which must be removed to construct an object in three dimensions. Each row or column has at most one integer on it, and the integer indicates how many cubes in the corresponding 1D slice remain when the object is complete. Kusano et al. showed that Picross 3D is NP-complete and Kimura et al. showed that the counting version, the another solution problem, and the fewest clues problem of Picross 3D are #P-complete, NP-complete, and Σ2P-complete, respectively, where those results are shown for the restricted input that the rectangular parallelepiped is of height four. On the other hand, Igarashi showed that Picross 3D is NP-complete even if the height of the input rectangular parallelepiped is one. Extending the result by Igarashi, we in this paper show that the counting version, the another solution problem, and the fewest clues problem of Picross 3D are #P-complete, NP-complete, and Σ2P-complete, respectively, even if the height of the input rectangular parallelepiped is one. Since the height of the rectangular parallelepiped of any instance of Picross 3D is at least one, our hardness results are best in terms of height.
In this study, product of two independent and non-identically distributed (i.n.i.d.) random variables (RVs) for κ-µ fading distribution and α-µ fading distribution is considered. The statistics of the product of RVs has been broadly applied in a large number of communications fields, such as cascaded fading channels, multiple input multiple output (MIMO) systems, radar communications and cognitive radios (CR). Exact close-form expressions of probability density function (PDF) and cumulative distribution function (CDF) with exact series formulas for the product of two i.n.i.d. fading distributions κ-µ and α-µ are deduced more accurately to represent the provided product expressions and generalized composite multipath shadowing models. Furthermore, ergodic channel capacity (ECC) is obtained to measure maximum fading channel capacity. At last, interestingly unlike κ-µ, η-µ, α-µ in [9], [17], [18], these analytical results are validated with Monte Carlo simulations and it shows that for provided κ-µ/α-µ model, non-linear parameter has more important influence than multipath component in PDF and CDF, and when the ratio between the total power of the dominant components and the total power of the scattered waves is same, higher α can significantly improve channel capacity over composite fading channels.
Takashi KONO Yasuhiko TAITO Hideto HIDAKA
Embedded system approaches to edge computing in IoT implementations are proposed and discussed. Rationales of edge computing and essential core capabilities for IoT data supply innovation are identified. Then, innovative roles and development of MCU and embedded flash memory are illustrated by technology and applications, expanding from CPS to big-data and nomadic/autonomous elements of IoT requirements. Conclusively, a technology roadmap construction specific to IoT is proposed.
This paper presents a compromising strategy based on constraint relaxation for automated negotiating agents in the nonlinear utility domain. Automated negotiating agents have been studied widely and are one of the key technologies for a future society in which multiple heterogeneous agents act collaboratively and competitively in order to help humans perform daily activities. A pressing issue is that most of the proposed negotiating agents utilize an ad-hoc compromising process, in which they basically just adjust/reduce a threshold to forcibly accept their opponents' offers. Because the threshold is just reduced and the agent just accepts the offer since the value is more than the threshold, it is very difficult to show how and what the agent conceded even after an agreement has been reached. To address this issue, we describe an explainable concession process using a constraint relaxation process. In this process, an agent changes its belief by relaxing constraints, i.e., removing constraints, so that it can accept it is the opponent's offer. We also propose three types of compromising strategies. Experimental results demonstrate that these strategies are efficient.
Boma A. ADHI Tomoya KASHIMATA Ken TAKAHASHI Keiji KIMURA Hironori KASAHARA
The advancement of multicore technology has made hundreds or even thousands of cores processor on a single chip possible. However, on a larger scale multicore, a hardware-based cache coherency mechanism becomes overwhelmingly complicated, hot, and expensive. Therefore, we propose a software coherence scheme managed by a parallelizing compiler for shared-memory multicore systems without a hardware cache coherence mechanism. Our proposed method is simple and efficient. It is built into OSCAR automatic parallelizing compiler. The OSCAR compiler parallelizes the coarse grain task, analyzes stale data and line sharing in the program, then solves those problems by simple program restructuring and data synchronization. Using our proposed method, we compiled 10 benchmark programs from SPEC2000, SPEC2006, NAS Parallel Benchmark (NPB), and MediaBench II. The compiled binaries then are run on Renesas RP2, an 8 cores SH-4A processor, and a custom 8-core Altera Nios II system on Altera Arria 10 FPGA. The cache coherence hardware on the RP2 processor is only available for up to 4 cores. The RP2's cache coherence hardware can also be turned off for non-coherence cache mode. The Nios II multicore system does not have any hardware cache coherence mechanism; therefore, running a parallel program is difficult without any compiler support. The proposed method performed as good as or better than the hardware cache coherence scheme while still provided the correct result as the hardware coherence mechanism. This method allows a massive array of shared memory CPU cores in an HPC setting or a simple non-coherent multicore embedded CPU to be easily programmed. For example, on the RP2 processor, the proposed software-controlled non-coherent-cache (NCC) method gave us 2.6 times speedup for SPEC 2000 “equake” with 4 cores against sequential execution while got only 2.5 times speedup for 4 cores MESI hardware coherent control. Also, the software coherence control gave us 4.4 times speedup for 8 cores with no hardware coherence mechanism available.
Chuzo IWAMOTO Tatsuaki IBUSUKI
Kurotto and Juosan are Nikoli's pencil puzzles. We study the computational complexity of Kurotto and Juosan puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.
Ryoma SENDA Yoshiaki TAKATA Hiroyuki SEKI
Register context-free grammars (RCFG) is an extension of context-free grammars to handle data values in a restricted way. In RCFG, a certain number of data values in registers are associated with each nonterminal symbol and a production rule has the guard condition, which checks the equality between the content of a register and an input data value. This paper starts with RCFG and introduces register type, which is a finite representation of a relation among the contents of registers. By using register type, the paper provides a translation of RCFG to a normal form and ϵ-removal from a given RCFG. We then define a generalized RCFG (GRCFG) where an arbitrary binary relation can be specified in the guard condition. Since the membership and emptiness problems are shown to be undecidable in general, we extend register type for GRCFG and introduce two properties of GRCFG, simulation and progress, which guarantee the decidability of these problems. As a corollary, these problems are shown to be EXPTIME-complete for GRCFG with a total order over a dense set.
Kenshiro SATO Dondee NAVARRO Shinya SEKIZAKI Yoshifumi ZOKA Naoto YORINO Hans Jürgen MATTAUSCH Mitiko MIURA-MATTAUSCH
The degradation of a SiC-MOSFET-based DC-AC converter-circuit efficiency due to aging of the electrically active devices is investigated. The newly developed compact aging model HiSIM_HSiC for high-voltage SiC-MOSFETs is used in the investigation. The model considers explicitly the carrier-trap-density increase in the solution of the Poisson equation. Measured converter characteristics during a 3-phase line-to-ground (3LG) fault is correctly reproduced by the model. It is verified that the MOSFETs experience additional stress due to the high biases occurring during the fault event, which translates to severe MOSFET aging. Simulation results predict a 0.5% reduction of converter efficiency due to a single 70ms-3LG, which is equivalent to a year of operation under normal conditions, where no additional stress is applied. With the developed compact model, prediction of the efficiency degradation of the converter circuit under prolonged stress, for which measurements are difficult to obtain and typically not available, is also feasible.
Hiroshi FUJIWARA Kei SHIBUSAWA Kouki YAMAMOTO Hiroaki YAMAMOTO
The multislope ski-rental problem is an online optimization problem that generalizes the classical ski-rental problem. The player is offered not only a buy and a rent options but also other options that charge both initial and per-time fees. The competitive ratio of the classical ski-rental problem is known to be 2. In contrast, the best known so far on the competitive ratio of the multislope ski-rental problem is an upper bound of 4 and a lower bound of 3.62. In this paper we consider a parametric version of the multislope ski-rental problem, regarding the number of options as a parameter. We prove an upper bound for the parametric problem which is strictly less than 4. Moreover, we give a simple recurrence relation that yields an equation having a lower bound value as its root.
Satoshi MATSUMOTO Tomoyuki UCHIDA Takayoshi SHOUDAI Yusuke SUZUKI Tetsuhiro MIYAHARA
A regular pattern is a string consisting of constant symbols and distinct variable symbols. The language of a regular pattern is the set of all constant strings obtained by replacing all variable symbols in the regular pattern with non-empty strings. The present paper deals with the learning problem of languages of regular patterns within Angluin's query learning model, which is an established mathematical model of learning via queries in computational learning theory. The class of languages of regular patterns was known to be identifiable from one positive example using a polynomial number of membership queries, in the query learning model. In present paper, we show that the class of languages of regular patterns is identifiable from one positive example using a linear number of membership queries, with respect to the length of the positive example.
Rui CHEN Ying TONG Ruiyu LIANG
Deep neural networks have achieved great success in visual tracking by learning a generic representation and leveraging large amounts of training data to improve performance. Most generic object trackers are trained from scratch online and do not benefit from a large number of videos available for offline training. We present a real-time generic object tracker capable of incorporating temporal information into its model, learning from many examples offline and quickly updating online. During the training process, the pre-trained weight of convolution layer is updated lagging behind, and the input video sequence length is gradually increased for fast convergence. Furthermore, only the hidden states in recurrent network are updated to guarantee the real-time tracking speed. The experimental results show that the proposed tracking method is capable of tracking objects at 150 fps with higher predicting overlap rate, and achieves more robustness in multiple benchmarks than state-of-the-art performance.
Tongxin YANG Toshinori SATO Tomoaki UKEZONO
Addition is a key fundamental function for many error-tolerant applications. Approximate addition is considered to be an efficient technique for trading off energy against performance and accuracy. This paper proposes a carry-maskable adder whose accuracy can be configured at runtime. The proposed scheme can dynamically select the length of the carry propagation to satisfy the quality requirements flexibly. Compared with a conventional ripple carry adder and a conventional carry look-ahead adder, the proposed 16-bit adder reduced the power consumption by 54.1% and 57.5%, respectively, and the critical path delay by 72.5% and 54.2%, respectively. In addition, results from an image processing application indicate that the quality of processed images can be controlled by the proposed adder. Good scalability of the proposed adder is demonstrated from the evaluation results using a 32-bit length.
Yoshitake OKI Yuto ABE Kazuki YAMAMOTO Kohei YAMAMOTO Tomoya SHIRAKAWA Akimasa YOSHIDA Keiji KIMURA Hironori KASAHARA
Utilization of local memory from real-time embedded systems to high performance systems with multi-core processors has become an important factor for satisfying hard deadline constraints. However, challenges lie in the area of efficiently managing the memory hierarchy, such as decomposing large data into small blocks to fit onto local memory and transferring blocks for reuse and replacement. To address this issue, this paper presents a compiler optimization method that automatically manage local memory of multi-core processors. The method selects and maps multi-dimensional data onto software specified memory blocks called Adjustable Blocks. These blocks are hierarchically divisible with varying sizes defined by the features of the input application. Moreover, the method introduces mapping structures called Template Arrays to maintain the indices of the decomposed multi-dimensional data. The proposed work is implemented on the OSCAR automatic parallelizing compiler and evaluations were performed on the Renesas RP2 8-core processor. Experimental results from NAS Parallel Benchmark, SPEC benchmark, and multimedia applications show the effectiveness of the method, obtaining maximum speed-ups of 20.44 with 8 cores utilizing local memory from single core sequential versions that use off-chip memory.
Tatsuya FUJII Kohsei ARAKI Kazuhiro SHOUNO
In this letter, an active complex filter with finite transmission zeros is proposed. In order to obtain a complex prototype ladder filter including no inductors, a new circuit transformation is proposed. This circuit is classified into the RiCR filter. It is shown that it includes no negative capacitors when it is obtained through a frequency transformation. The validity of the proposed method is confirmed through computer simulation.
Fanxin ZENG Xiping HE Guixin XUAN Zhenyu ZHANG Yanni PENG Li YAN
In an OFDM communication system using quadrature amplitude modulation (QAM) signals, peak envelope powers (PEPs) of the transmitted signals can be well controlled by using QAM Golay complementary sequence pairs (CSPs). In this letter, by making use of a new construction, a family of new 16-QAM Golay CSPs of length N=2m (integer m≥2) with binary inputs is presented, and all the resultant pairs have the PEP upper bound 2N. However, in the existing such pairs from other references their PEP upper bounds can arrive at 3.6N when the worst case happens. In this sense, novel pairs are good candidates for OFDM applications.
Andros TJANDRA Sakriani SAKTI Satoshi NAKAMURA
Recurrent Neural Network (RNN) has achieved many state-of-the-art performances on various complex tasks related to the temporal and sequential data. But most of these RNNs require much computational power and a huge number of parameters for both training and inference stage. Several tensor decomposition methods are included such as CANDECOMP/PARAFAC (CP), Tucker decomposition and Tensor Train (TT) to re-parameterize the Gated Recurrent Unit (GRU) RNN. First, we evaluate all tensor-based RNNs performance on sequence modeling tasks with a various number of parameters. Based on our experiment results, TT-GRU achieved the best results in a various number of parameters compared to other decomposition methods. Later, we evaluate our proposed TT-GRU with speech recognition task. We compressed the bidirectional GRU layers inside DeepSpeech2 architecture. Based on our experiment result, our proposed TT-format GRU are able to preserve the performance while reducing the number of GRU parameters significantly compared to the uncompressed GRU.
Huiyao ZHENG Jian SHEN Youngju CHO Chunhua SU Sangman MOH
Cloud computing is a unlimited computing resource and storing resource, which provides a lot of convenient services, for example, Internet and education, intelligent transportation system. With the rapid development of cloud computing, more and more people pay attention to reducing the cost of data management. Data sharing is a effective model to decrease the cost of individuals or companies in dealing with data. However, the existing data sharing scheme cannot reduce communication cost under ensuring the security of users. In this paper, an anonymous and traceable data sharing scheme is presented. The proposed scheme can protect the privacy of the user. In addition, the proposed scheme also can trace the user uploading irrelevant information. Security and performance analyses show that the data sharing scheme is secure and effective.
Yudai SAKAMOTO Shigeru YAMASHITA
In Stochastic Computing (SC), we need to generate many stochastic numbers (SNs). If we generate one SN conventionally, we need a Stochastic Number Generator (SNG) which consists of a linear-feedback shift register (LFSR) and a comparator. When we calculate an arithmetic function by SC, we need to generate many SNs whose values are equal to constant values used in the arithmetic function. As a consequence, the hardware overhead becomes huge. Accordingly, there has been proposed a method called GMCS (Generating Many Constant SNs from Few SNs) to generate many constant SNs with low hardware overhead. However, if we use GMCS simply, generated constant SNs are correlated highly with each other. This would be a serious problem because the high correlation of SNs make a large error in computation. Therefore, in this paper, we propose efficient methods to generate constant SNs with reasonably low hardware overhead without increasing errors. To reduce the correlations of constant SNs which are generated by GMCS, we use Register based Re-arrangement circuit using a Random bit stream duplicator (RRRD). RRRDs have few influences on the hardware overhead because an RRRD consists of three multiplexers (MUXs) and two 1-bit FFs. We also use a technique to share random number generators with several SNGs to reduce the hardware overhead. We provide some experimental results by which we can confirm that our proposed methods are in general very useful to reduce the hardware overhead for generating constant SNs without increasing errors.