Biplab KUMER SARKER Anil KUMAR TRIPATHI Deo PRAKASH VIDYARTHI Kuniaki UEHARA
A Distributed Computing System (DCS) contributes in proper partitioning of the tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processing nodes of the system. The scheduling of various modules on particular processing nodes may be preceded by appropriate allocation of modules of the different tasks to various processing nodes and then only the appropriate execution characteristic can be obtained. A number of algorithms have been proposed for allocation of tasks in a DCS. Most of the solutions proposed had simplifying assumptions. The very first assumption has been: consideration of a single task with their corresponding modules only; second, no consideration of the status of processing nodes in terms of the previously allocated modules of various tasks and third, the capacity and capability of the processing nodes. This work proposes algorithms for a realistic situation wherein multiple tasks with their modules compete for execution on a DCS dynamically considering their architectural capability. In this work, we propose two algorithms based on the two well-known A* and GA for the task allocation models. The paper explains the algorithms elaborately by illustrated examples and presents a comparative performance study among our algorithms and the algorithms for task allocation proposed in the various literatures. The results demonstrate that our GA based task allocation algorithm achieves better performance compared with the other algorithms.
Jianliang XU Yong CHEN Tsunehiro YOSHINAGA Katsushi INOUE
This paper introduces a 1-inkdot two-way alternating pushdown automaton which is a two-way alternating pushdown automaton (2apda) with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. We first investigate a relationship between the accepting powers of sublogarithmically space-bounded 2apda's with and without 1 inkdot, and show, for example, that sublogarithmically space-bounded 2apda's with 1 inkdot are more powerful than those which have no inkdots. We next investigate an alternation hierarchy for sublogarithmically space-bounded 1-inkdot 2apda's, and show that the alternation hierarchy on the first level for 1-inkdot 2apda's holds, and we also show that 1-inkdot two-way nondeterministic pushdown automata using sublogarithmic space are incomparable with 1-inkdot two-way alternating pushdown automata with only universal states using the same space.
Probabilistic encryption becomes more and more important since its ability to against chosen-ciphertext attack. Applications like online voting schemes and one-show credentials are based on probabilistic encryption. Research on good probabilistic encryptions are on going, while many good deterministic encryption schemes are already well implemented and available in many systems. To convert any deterministic encryption scheme into a probabilistic encryption scheme, a randomized media is needed to apply on the message and carry the message over as an randomized input. In this paper, nonlinear codes obtained by certain mapping from linear error-correcting codes are considered to serve as such carrying media. Binary nonlinear codes obtained by Gray mapping from
Hosang YUN Kwangwook SHIN Hyunsoo YOON
The crucial handover elements in wireless ATM networks are handover delay and handover efficiency. Since the research about the handover in wireless ATM has until now focused mainly on minimizing handover delay, the results have shown the inefficiency of network resources. In broadband wireless ATM networks, handover efficiency is critical to network capacity. In this paper, we propose a new handover scheme based on a partial path rerouting scheme called the delay limited best-fit backtracking scheme. The scheme searches for the crossover switch that limits handover delay and at the same time maximizes handover efficiency. It uses a new crossover switch searching method, which is an adaptive backtracking searching method that uses a best-fit search manner, to search for the optimal crossover switch that satisfies the given crossover switch condition. We evaluated the performance of proposed handover scheme, and show that the suggested scheme can improve handover efficiency more than other handover schemes.
This paper proposes a novel CMOS built-in current sensor (BICS) for on-line current testing. Proposed BICS detects abnormal current in circuit under test (CUT) and makes a Pass/Fail signal through comparison between the CUT current and the duplicated inverter current. This circuit consists of two current-to-voltage conversion transistors, a full swing generator, a voltage comparator, and an inverter block. It requires 16 transistors. Since this BICS does not require the extra clock, the added extra pin is only one output pin. Furthermore, the BICS does not require test mode selection. Therefore the BICS can be applied to on-line current testing. The validity and effectiveness are verified through the HSPICE simulation of circuits with defects. When the CUT is an 8 8 parallel multiplier, the area overhead of the BICS is about 4.34%.
Takuma ISHIDA Tatsuumi SOYAMA Shogo MURAMATSU Hisakazu KIKUCHI Tetsuro KUGE
In this paper, a lifting implementation of variable-coefficient invertible deinterlacer with embedded motion detector is proposed. As previous works, the authors have developed invertible deinterlacing that suppresses comb-tooth artifacts caused by field interleaving for interlaced scanning video, which affect the quality of intraframe-based codec such as Motion-JPEG2000. To improve the local adaptability for given pictures, its variable-coefficient processing with motion detection has also been proposed so that filters can be changed according to local properties of motion pictures, while maintaining the invertibility. In this paper, it is shown that the variable-coefficient invertible deinterlacing can be realized by a lifting-based simple hardware architecture, and motion detector can also be embedded. Both of the motion detection and deinterlacing filters are shared by a special choice of their coefficients, and by adaptive selection of deinterlacing filters. The significance of our proposed architecture is verified by showing synthesis results from the VHDL models. The proposed implementation with embedded motion detector achieves about 28% reduction of the gate count compared with the corresponding separate implementation.
Katsumi MORISHITA Shi Feng YUAN Yoshihiro MIYAKE Takahiro FUJIHARA
It is shown that the glass structure change is a simple and widely applicable method to modify refractive index locally in various glass fibers. A small part of a glass fiber is heated immediately to above its melt temperature by arc discharge, and then the molten fiber undergoes rapid cooling, which freezes the change of the glass structure. Therefore the refractive index of the fiber is decreased partially by the glass structure change induced by rapid solidification. The index reduction in a fiber fabricated from multicomponent glasses is estimated to be more than 0.006. To clarify that rapid solidification works for various glasses including silica glasses, long-period gratings are written in a standard telecommunication fiber with various discharge currents and times. The peak loss of more than 25 dB is obtained within only 6 periods. The index change can be adjusted by the discharge conditions. The gratings are not degraded by heating the whole gratings at 700C for 2 hours, and are highly temperature-stable. It is shown that resonance wavelengths can be tuned by controlling the heating temperature and heating time.
Michihiro AOKI Miki HIRANO Nobuaki MATSUURA Takashi KURIMOTO Takashi MIYAMURA Masahiro GOSHIMA Keisuke KABASHIMA Shigeo URUSHIDANI
The growth in the volume of Internet traffic and the increasing variety of Internet applications require Internet backbone networks to be scalable and provided sophisticated quality of service (QoS) capabilities. Internet backbone routers have evolved to achieve sub-Tbps switching capacity in a single unit, but their switch architectures have limited scalability, causing QoS to degrade as the switches get bigger. Hence, we propose a large-scale IP and lambda integrated router architecture with scalable switches. We first describe the system architecture of our proposed backbone router and clarify the requirements for its switching capabilities to meet near-future demands. The new switch architecture, using crossbar-based switching fabrics and optical interconnection devices, meets the requirements for a backbone router to scale up to 82 Tbps and enable light path switching as well as packet switching. The routing tag and its usage algorithm in the switch, and packaging issues, including the quantity of hardware required for expansion, are also discussed.
Sebastien NUTTINCK Edward GEBARA Stephane PINEL Joy LASKAR
We report the investigation of major dispersion mechanisms such as self-heating, trapping, current collapse, and floating-body effects present in AlGaN/GaN HFETs. These effects are analyzed using DC/Pulsed IV, load-pull, low-frequency noise systems, and a cryogenic probe station. This study leads to a better understanding of the device physics, which is critical for accurate large-signal modeling and device optimization.
Akira INOUE Shigenori NAKATSUKA Satoshi SUZUKI Kazuya YAMAMOTO Teruyuki SHIMURA Ryo HATTORI Yasuo MITSUI
A microwave waveform measurement system below 18 GHz was developed and verified with a conventional RF measurement. The current and voltage RF waveforms of AlGaAs HBTs at the fundamental frequency of 1 GHz were directly measured with the system. A new direct method of sweeping and measuring dynamic RF load lines is proposed to measure the operating limits of the device. The maximum operating region was experimentally investigated with this method. The limits with a small input power are found to come from thermal runaway and the avalanche breakdown of the device. With a large input power, the HBT was found to operate beyond the DC limit of thermal runaway. The base ballasting resistance was also found to enhance large signal operating limits beyond those expected from the conventional DC theory.
Borja VIDAL Valentín POLO Juan L. CORRAL Javier MARTI
In this paper, a novel flexible photonic microwave filter architecture based on the use of laser arrays and the periodicity of N N arrayed waveguide gratings (AWG) optical response is proposed. Independent filter response coarse and fine tuning as well as reshaping of each transversal filter response have been experimentally demonstrated showing an excellent agreement with theory.
Jose MORA Beatriz ORTEGA Miguel V. ANDRES Jose CAPMANY Jose Luis CRUZ Daniel PASTOR Salvador SALES
In this paper, we propose a new configuration to implement transversal filters with negligible temperature sensitivity and low cost. These microwave filters are based on uniform fibre Bragg gratings as slicing elements of a broadband optical source. By using a tapered fibre Bragg grating as a delay line, we show that the temperature effects are the same over each component of the RF-filter. Therefore, it is possible a total cancellation of the thermal effects. The performance of these filters is compared to previous techniques, such as a laser array approach.
Takashi HASHIMOTO Shunichi KUROMARU Masayoshi TOUJIMA Yasuo KOHASHI Masatoshi MATSUO Toshihiro MORIIWA Masahiro OHASHI Tsuyoshi NAKAMURA Mana HAMADA Yuji SUGISAWA Miki KUROMARU Tomonori YONEZAWA Satoshi KAJITA Takahiro KONDO Hiroki OTSUKI Kohkichi HASHIMOTO Hiromasa NAKAJIMA Taro FUKUNAGA Hiroaki TOIDA Yasuo IIZUKA Hitoshi FUJIMOTO Junji MICHIYAMA
A low power MPEG-4 video codec LSI with the capability for core profile decoding is presented. A 16-b DSP with a vector pipeline architecture and a 32-b arithmetic unit, eight dedicated hardware engines to accelerate MPEG-4 SP@L1 codec, CP@L1 decoding and post video processing, 20-Mb embedded DRAM, and three peripheral blocks are integrated together on a single chip. MPEG-4 SP@L1 codec, CP@L1 decoding and post video processing are realized with a hybrid architecture consisting of a programmable DSP and dedicated hardware engines at low operating frequency. In order to reduce the power consumption, clock gating technique is fully adopted in each hardware block and embedded DRAM is employed. The chip is implemented using 0.18-µm quad-metal CMOS technology, and its die area is 8.8 mm 8.6 mm. The power consumption is 90 mW at a SP@L1 codec and 110 mW at a CP@L1 decoding.
Daryoosh SAEEDKIA A. Hamed MAJEDI S. SAFAVI-NAEINI Raafat R. MANSOUR
This paper presents a novel mm-wave and THz device concept, with a detailed physical modeling and quantitative performance evaluation, called as CW HTS (high temperature superconductive) photomixer/antenna. Optical heterodyne photomixing in the DC-biased HTS strip has been employed to create mm-wave and THz signal, and the size of strip on the grounded dielectric substrate is designed to have an efficient broadside radiation. Incorporating the HTS microstrip configuration as both photomixing media and radiation element at the same time not only increases the CW photocurrent but also the radiation power, while it reduces the radiation loss associated with the patch antenna. Two possible configurations called as longitudinal and transversal will be introduced and their photomixing efficiency and output radiation power will be compared. The detailed analysis along with the optimum design of the geometrical parameters of the microstrip structure shows that the transversal scheme exhibits higher radiation power. The typical nW output power can be obtained by mW laser pump power for frequencies up to the gap frequency of the HTS material. The output power of the proposed device is theoretically higher than the experimentally available data from a Low-Temperature-Grown (LTG) GaAs photomixer integrated with dipole or bow-tie antenna reported in the literature.
Sabarni PALIT Mark JAEGER Sergio GRANIERI Azad SIAHMAKOUN Bruce BLACK Jeffrey CHESTNUT
Binary and ternary 5-bit programmable dispersion matrix, based on fiber Bragg reflectors, is built to control a two-channel receive/transmit beamformer at 1550 nm. RF phase measurements for the 32/31 delay configurations are presented. The programmable dispersion matrix is fully demonstrated and characterized for RF signals from 0.2 to 1 GHz.
Kyue-Sup BYUN Sung-Hwa LIM Jai-Hoon KIM
This paper presents a two-tier coordinated checkpointing algorithm which can reduce the number of messages by being composed of two levels in mobile computing. Thus mobile devices have a high mobility and are lack of resources (e.g., storage, bandwidth, and battery power), traditional distributed algorithms like coordinated checkpointing algorithms could not be applied properly in mobile environment. In our proposed two-tier coordinated checkpointing algorithm, the messages to be transferred are requested by the mobile hosts and are handled by the appropriate MSS's (Mobile Support Stations). And the broadcast messages are handled by MSS instead of relaying the messages to all the mobile hosts directly as with the previous algorithms. This can reduce the communication cost and maintain the overall system consistency. In wireless cellular network, mobile computing based on a two-tier coordinated checkpointing algorithm reduces the number of synchronization messages. We perform performance comparisons by parametric analysis to show that a two-tier coordinated checkpointing algorithm can reduce communication cost compared to the previous algorithms in which the messages are directly sent to the mobile hosts.
Kouki NAGAMUNE Kazuhiko TANIGUCHI Syoji KOBASHI Yutaka HATA
This paper proposes an automated 3D visualization method of embedded tubes applicable to the scanned result of pulse-radar Non-Destructive Testing (NDT). The proposed method consists of three stages. First, our method defines the processing region which includes a pattern generated by a tube. This region is determined by referring to the composition of a received wave. Second, after expert knowledge of a tube is translated into fuzzy inference rules, the positions of embedded tubes are identified by inferring them. Third, 3D links of the identified positions are formed to visualize the continuous shape of the tubes. Consequently, the tubes are extracted, and their 3D shapes are visualized. The experimental result on the specimens shows that our method was able to find all tubes that exist in the radiograph and the schematic. Our method could thus provide the internal information of concrete with sufficient accuracy required in the practical construction work.
Masaya FUJISAWA Shusuke MAEDA Shojiro SAKATA
A compound error is any combination of burst errors with various burst lengths including random errors. The compound weight of any such error is defined as a kind of combinational metric which is a generalization of Gabidulin's metric. First, we present a fast method for calculating the weight of any word. Based on this method, as an extension of Wadayama's augmenting method in the case of Hamming weight, we propose a method of constructing codes having higher coding rate by augmenting any compound-error-correcting codes. Furthermore, we show some examples of good compound-error-correcting codes obtained by using our augmenting method.
Zhang-Jian LI Shin-ichi NAKANO
A "rooted" plane triangulation is a plane triangulation with one designated vertex r and one designated edge incident to r on the outer face. In this paper we give a simple algorithm to generate all connected rooted plane triangulations with at most m edges. The algorithm uses O(m) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all connected (non-rooted) plane triangulations with at most m edges in O(m3) time per triangulation.
Tomoyuki OHTA Shinji INOUE Yoshiaki KAKUDA Kenji ISHIDA
A clustering scheme for ad hoc networks is aimed at managing a number of mobile devices by utilizing hierarchical structure of the networks. In order to construct and maintain an effective hierarchical structure in ad hoc networks where mobile devices may move at high mobility, the following requirements must be satisfied. (1) The role of each mobile device for the hierarchical structure is adaptive to dynamic change of the topology of the ad hoc networks. The role of each mobile device should thus change autonomously based on local information in each mobile device. (2) The overhead for management of the hierarchical structure is small. The number of mobile devices in each cluster should thus be almost equivalent. This paper proposes an adaptive multihop clustering scheme for highly mobile ad hoc networks. The results obtained by extensive simulation experiments show that the proposed scheme does not depend on mobility and node degree of mobile devices in the network, which satisfy the above requirements.