Viable techniques such as dynamic voltage scaling (DVS) provide a new design technique to balance system performance and energy saving. In this paper, we extend previous works on task assignment problems for a set of linear-pipeline tasks over a set of processors. Different from previous works, we revisit the problems with two additional system factors: deadline and energy-consumption, which are key factors in real-time and power-aware computation. We propose an O(nm2) time complexity algorithm to determine optimal task-assignment and speed-setting schemes leading to minimal energy consumption, for a given set of m real-time tasks running on n identical processors (with or without DVS supports). The same result can be extended to a restricted form of heterogeneous processor model. Meanwhile, we show that on homogeneous processor model more efficient algorithms can be applied and result in time complexity of O(m2) when m ≤ n. For completeness, we also discuss cases without contiguity constraints. We show under such cases the problems become at least as hard as NP-hard.
Yusuke AYATO Akiko TAKATSU Kenji KATO Naoki MATSUDA
In situ observations were mainly performed by using slab optical waveguide (SOWG) spectroscopy synchronized with potential step measurements to investigate the time dependent spectral change of the adsorbed heptyl viologen cation radicals (HV+
Masayoshi AIKAWA Eisuke NISHIYAMA Takayuki TANAKA
This paper presents an advanced and extensive utilization approach of microwave resonant fields, and the applications to push-push oscillators and reconfigurable planar antennas. The excellent coherency, synchronous harmonics and the degenerative orthogonal modes of electromagnetic field built up on microwave resonators are noticeable features in this approach. Another crucial point is the resonant field controllability that is especially essential feature for reconfigurable antennas in this paper. All the features can be realized by embedding semiconductor devices and/or IC's on a microwave resonator. Push-push oscillators and reconfigurable planar antennas are described as good examples of this approach. The push-push oscillators can generate very higher frequency signals due to the selective use of the 4th harmonic up to the 8th harmonic resonant fields, suppressing undesired harmonic signals. As a result, very high frequency band oscillators up to millimeter-wave bands with good suppression of undesired harmonic signals can be easily realized at very low cost by use of commercially available active devices for low frequency bands. The reconfigurable planar antennas are also demonstrated, where the boundary condition of the resonant field on planar antennas can be purposefully controlled to realize reconfigurable antenna performances by the semiconductor devices embedded on the patch as well. The orthogonal linear polarization controllable patch, the dual-band switching patch and the continuously frequency controllable patch have been demonstrated as the successful applications of this approach.
Tokio KANEDA Atsushi SANADA Hiroshi KUBO
A novel two-dimensional (2D) beam scanning antenna array using composite right/left-handed (CRLH) leaky-wave antennas (LWAs) is proposed. The antenna array consists of a set of CRLH LWAs and a Butler matrix (BM) feeding network. The direction of the beam can be scanned two-dimensionally in one plane by changing frequency and in the other plane by switching the input ports of the BM. A four-element antenna array in the microstrip line configuration operating at 10.5 GHz is designed with the assistance of full-wave simulations based on the method of moment (MoM) and the finite-element method (FEM). The antenna array is fabricated and radiation characteristics are measured. The wide range 2D beam scanning operation with the angle from -30 deg to +25 deg in one plane by sweeping frequency from 10.25 GHz to 10.7 GHz and with four discrete angles of -46 deg, -15 deg, +10 deg, and +35 deg in the other plane by switching the input port is achieved.
Shinji KINOSHITA Akihiro TOMIOKA Atsushi FUJIMOTO Yasuaki ITAKURA
Self-organized organic dye particles of micrometer and submicrometer size were prepared by utilizing a wetting/dewetting process of polar solvent on a hydrophilic glass substrate. The near-field scanning optical microscopy successfully identified near-field excited near-field fluorescence from single particles, however, the majority of the small particles with diameters around 2 µm or less did not show fluorescence under near-field observation. In contrast, far-field fluorescence, when excited by a polarized evanescent field, was observed, with the intensity depending on the excitation polarization, indicating that molecules' transition moment within dye particles was oriented parallel to the substrate surface. Single particle fluorescence spectrum consistently showed an identical sharp peak with a large redshift, indicating that the particles were composed of identical dye aggregates similar to J-aggregates. These observations suggest that the near-field at the probe tip was polarized parallel to the probe axis. Another observation, that molecules were oriented in a similar direction among adjacent particles, suggests that the dewetting process contributed to the alignment of the molecular orientation among adjacent particles, which further proves that the present specimen was formed by a self-organizing mechanism.
Kentaro KAWAKAMI Jun TAKEMURA Mitsuhiko KURODA Hiroshi KAWAGUCHI Masahiko YOSHIMOTO
We propose an elastic pipeline that can apply dynamic voltage scaling (DVS) to hardwired logic circuits. In order to demonstrate its feasibility, a hardwired H.264/AVC HDTV decoder is designed as a real-time application. An entropy decoding process is divided into context-based adaptive binary arithmetic coding (CABAC) and syntax element decoding (SED), which has advantages of smoothing workload for CABAC and keeping efficiency of the elastic pipeline. An operating frequency and supply voltage are dynamically modulated every slot depending on workload of H.264 decoding to minimize power. We optimize the number of slots per frame to enhance power reduction. The proposed decoder achieves a power reduction of 50% in a 90-nm process technology, compared to the conventional clock-gating scheme.
Sangchul HAN Heeheon KIM Xuefeng PIAO Minkyu PARK Seongje CHO Yookun CHO
This letter proves the finish time predictability of EDZL (Earliest Deadline Zero Laxity) scheduling algorithm for multiprocessor real-time systems, which is a variant of EDF. Based on the results, it also shows that EDZL can successfully schedule any periodic task set if its total utilization is not greater than (m+1)/2, where m is the number of processors.
Shinobu NAGAYAMA Tsutomu SASAO Jon T. BUTLER
This paper presents an architecture and a synthesis method for compact numerical function generators (NFGs) for trigonometric, logarithmic, square root, reciprocal, and combinations of these functions. Our NFG partitions a given domain of the function into non-uniform segments using an 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. Experimental results show that: 1) our NFGs require, on average, only 4% of the memory needed by NFGs based on the linear approximation with non-uniform segmentation; 2) our NFG for 2x-1 requires only 22% of the memory needed by the NFG based on a 5th-order approximation with uniform segmentation; and 3) our NFGs achieve about 70% of the throughput of the existing table-based NFGs using only a few percent of the memory. Thus, our NFGs can be implemented with more compact FPGAs than needed for the existing NFGs. Our automatic synthesis system generates such compact NFGs quickly.
Hiroki NAKAHARA Tsutomu SASAO Munehiro MATSUURA
This paper represents a cycle-based logic simulation method using an LUT cascade emulator, where an LUT cascade consists of multiple-output LUTs (cells) connected in series. The LUT cascade emulator is an architecture that emulates LUT cascades. It has a control part, a memory for logic, and registers. It connects the memory to registers through a programmable interconnection circuit, and evaluates the given circuit stored in the memory. The LUT cascade emulator runs on an ordinary PC. This paper also compares the method with a Levelized Compiled Code (LCC) simulator and a simulator using a Quasi-Reduced Multi-valued Decision Diagram (QRMDD). Our simulator is 3.5 to 10.6 times faster than the LCC, and 1.1 to 3.9 times faster than the one using a QRMDD. The simulation setup time is 2.0 to 9.8 times shorter than the LCC. The necessary amount of memory is 1/1.8 to 1/5.5 of the one using a QRMDD.
Toshiyuki MIYAMOTO Yasuhiro MORITA Sadatoshi KUMAGAI
Secret sharing is a method for distributing a secret among a party of participants. Each of them is allocated a share of the secret, and the secret can only be reconstructed when the shares are combined together. We have been proposing a secret sharing distributed database system (SSDDB) that uses a secret sharing scheme to improve confidentiality and robustness of distributed database systems. This paper proposes a vertical partitioning algorithm for the SSDDB, and evaluates the algorithm by computational experiments.
Won-Sup CHUNG Seong-Hoon KIM Sang-Hee SON Hee-jun KIM
A novel linear transconductor using translinear cells is proposed. It consists of a voltage follower, a resistor, and a current follower. SPICE simulations using an 8 GHz bipolar transistor-array parameter show that the linear transconductor with a transconductance of 1 mS exhibits a linearity error of less than 0.75% over an input voltage range of 1 V for a supply voltage of 2.0 V. The temperature coefficient of the transconductance is less than 124 ppm/. The -3-dB frequency of the transconductance is more than 4.5 GHz. Applying the linear transconductor as a building block, the design of a bandpass filter with center frequency of 85 MHz and Q-factor of 80 is presented.
Jun UCHITA Shogo MURAMATSU Takuma ISHIDA Hisakazu KIKUCHI
In this paper, a coefficient-parameter embedding method into Motion-JPEG2000 (MJP2) is proposed for invertible deinterlacing with variable coefficients. Invertible deinterlacing, which the authors have developed before, can be used as a preprocess of frame-based motion picture codec, such as MJP2, for interlaced videos. When the conventional field-interleaving is used instead, comb-tooth artifacts appear around edges of moving objects. On the other hand, the invertible deinterlacing technique allows us to suppress the comb-tooth artifacts and also guaranties recovery of original pictures. As previous works, the authors have developed a variable coefficient scheme with a motion detector, which realizes adaptability to local characteristics of given pictures. However, when this deinterlacing technique is applied to a video codec, coefficient parameters have to be sent to receivers for original picture recovery. This paper proposes a parameter-embedding technique in MJP2 and constructs a standard stream which consists both of picture data and the parameters. The parameters are embedded into the LH1 component of wavelet transform domain through the ROI (region of interest) function of JPEG2000 without significant loss in the performance of comb-tooth suppression. Some experimental results show the feasibility of our proposed scheme.
Noriaki ODA Hiroyuki KUNISHIMA Takashi KYOUNO Kazuhiro TAKEDA Tomoaki TANAKA Toshiyuki TAKEWAKI Masahiro IKEDA
A novel wiring design concept called "Triple Damascene" is presented. We propose a new technology to mix wirings with different thickness in one layer by using dual damascene process without increasing mask steps. In this technology, three types of grooves are opened simultaneously. Deep trenches for thick wires, as well as vias and shallow trenches, are selectively opened. By the design concept using this technology, a 30% reduction in wiring delay is obtained for critical path. A 5% reduction in chip size is also obtained as the effect of decrease in repeater number for a typical high-performance multi-processing unit (MPU) in 0.13 µm generation. An example for performance enhancement in an actual product of graphic MPU chip is also demonstrated.
Masanori HARIYAMA Shigeo YAMADERA Michitaka KAMEYAMA
This paper presents a design method to minimize energy of both functional units (FUs) and an interconnection network between FUs. To reduce complexity of the interconnection network, data transfers between FUs are classified according to FU types of operations in a data flow graph. The basic idea behind reducing the complexity of the interconnection network is that the interconnection resource can be shared among data transfers with the same FU type of a source node and the same FU type of a destination node. Moreover, an efficient method based on a genetic algorithm is presented.
Todor COOKLEV Akinori NISHIHARA
An analytic approach for the generation of non-periodic and periodic complementary sequences is advanced for lengths that are powers of two. The periodic complementary sequences can be obtained using symmetric or anti-symmetric extensions. The properties of their autocorrelation functions are studied. The non-periodic complementary sequences are the intersection between anti-symmetric and symmetric periodic sequences. These non-periodic and periodic complementary sequences are identified to be special cases of non-periodic and periodic (or cyclic) orthogonal wavelet transforms. This relationship leads to the novel approach.
Da-Ren CHEN Chiun-Chieh HSU Chien-Min WANG
A hard real-time system is one whose correctness depends not only on the logical result, but also when the results are produced. While many techniques have been proposed for single processor real-time systems, multiprocessor systems have not been studied so extensively. In this paper, we mainly propose two variant (DCTS) by using the Early-Release-Fair (ERfair) and Proportionate-fair (Pfair) model with integral assumptions for identical multi-processor real-time systems. ERfair is a scheduling model for real-time tasks on a multiprocessor system. On the different definitions of distance constraint, we propose two efficient scheduling algorithms designed to probe whether the distance constraints of all ER-fair tasks can be guaranteed. If the distance constraints cannot be guaranteed, then the proposed algorithms gather the unfeasible tasks and inflate them with a reweighting function. The proposed algorithms are linear-time and most suitable for dynamic systems. The experimental results reveal that the proposed algorithms increase significantly the ratio of schedulable task sets.
Ayman HAGGAG Mohamed GHONEIM Jianming LU Takashi YAHAGI
In this paper, we first briefly discuss the newly emerging Secured JPEG (JPSEC) standard for security services for JPEG 2000 compressed images. We then propose our novel approach for applying authentication to JPEG 2000 images in a scalable manner. Our authentication technique can be used for source authentication, nonrepudiation and integrity verification for the received possibly transcoded JPEG 2000 images in such a way that it is possible to authenticate different resolutions or different qualities extracted or received from a JPEG 2000 encoded image. Three different implementation methods for our authentication technique are presented. Packet-Based Authentication involves using the MD5 hashing algorithm for calculating the hash value for each individual packet in the JPEG 2000 codestream. Hash values are truncated to a specified length to reduce the overhead in storage space, concatenated into a single string, and then signed using the RSA algorithm and the author's private key for repudiation prevention. Resolution-Based Authentication and Quality-Based Authentication methods involve generating a single hash value from all contiguous packets from each entire resolution or each entire quality layer, respectively. Our algorithms maintain most of the inherent flexibility and scalability of JPEG 2000 compressed images. The resultant secured codestream is still JPEG 2000 compliant and compatible with JPEG 2000 compliant decoders. Also, our algorithms are compatible with the Public Key Infrastructure (PKI) for preventing signing repudiation from the sender and are implemented using the new JPSEC standard for security signaling.
Morikazu NAKAMURA Koji HACHIMAN Hiroki TOHME Takeo OKAZAKI Shiro TAMAKI
This paper considers Cyclic Job-Shop Scheduling Problems (CJSSP) extended from the Job-Shop Scheduling Problem (JSSP). We propose an evolutionary computing method to solve the problem approximately by generating the Petri net structure for scheduling. The crossover proposed in this paper employs structural analysis of Petri net model, that is, the crossover improves the cycle time by breaking the bottle-neck circuit obtained by solving a linear programming problem. Experimental evaluation shows the effectiveness of our approach.
A dynamically reconfigurable device is a device that can change its hardware configuration arbitrarily often in order to achieve the desired performance and functions. Since several tasks are executed on the device concurrently, scheduling of both task execution and reconfiguration is an important problem. In our model, the dynamically reconfigurable device is represented by a two-level hierarchical automaton, and execution of each periodic task is represented by a timed discrete event system. We propose a composition rule to get an automaton, which represents non-preemptive execution of periodic tasks on the dynamically reconfigurable device. We introduce a method to get a feasible execution sequence of tasks by using state feedback control.
In this paper, we present a scheduler that incorporates round robin service within a VirtualClock discipline. Time-stamp based scheduling algorithms attain a low local delay bound and performance guarantee, but are computationally complex. On the other hand, round robin schemes are simple to implement and have computational complexity of O(1), but they are well known for their output burstiness and short-term unfairness. In order to overcome this problem, we combine round robin with VirtualClock in an algorithm we call VCRR. VCRR possesses better fairness than simple round robin, low jitter and a good scheduling delay bound. At the same time, VCRR preserves the O(1) time complexity of round robin. Simulation experiments show VCRR's efficiency in terms of delay performance, jitter and fairness.