A feedback node set (FNS) of a graph is a subset of the nodes of the graph whose deletion makes the residual graph acyclic. By finding an FNS in an interconnection network, we can set a check point at each node in it to avoid a livelock configuration. Hence, to find an FNS is a critical issue to enhance the dependability of a parallel computing system. In this paper, we propose a method to find FNS's in n-pancake graphs and n-burnt pancake graphs. By analyzing the types of cycles proposed in our method, we also give the number of the nodes in the FNS in an n-pancake graph, (n-2.875)(n-1)!+1.5(n-3)!, and that in an n-burnt pancake graph, 2n-1(n-1)!(n-3.5).

Incorporating a tool for administering medication, such as a syringe, is required in microneedles (MNs) for medical use. This renders it easier for non-medical personnel to administer medication. Because it is difficult to fabricate a hollow MN, we fabricated a capillary groove on an MN and its substrate to enable the administration of a higher dosage. MN grooving is difficult to accomplish via the conventional injection molding method used for polylactic acid. Therefore, biodegradable polyacid anhydride was selected as the material for the MN. Because polyacid anhydride is a low-viscosity liquid at room temperature, an MN can be grooved using a processing method similar to vacuum casting. This study investigated the performance of the capillary force of the MN and the optimum shape and size of the MN by a puncture test.

Recently, we introduced a new automata model, so-called colored finite automata (CFAs) whose accepting states are multi-colored (i.e., not conventional black-and-white acceptance) in order to classify their input strings into two or more languages, and solved the specific complexity problems concerning color-unmixedness of nondeterministic CFA. That is, so-called UV, UP, and UE problems are shown to be NLOG-complete, P, and NP-complete, respectively. In this paper, we apply the concept of colored accepting mechanism to pushdown automata and show that the corresponding versions of the above-mentioned complexity problems are all undecidable. We also investigate the case of unambiguous pushdown automata and show that one of the problems turns out to be permanent true (the others remain undecidable).

In a smart home environment, sensors generate events whenever activities of residents are captured. However, due to some factors, abnormal events could be generated, which are technically reasonable but contradict to real-world activities. To detect abnormal events, a number of methods has been introduced, e.g., clustering-based or snapshot-based approaches. However, they have limitations to deal with complicated anomalies which occur with large number of events and blended within normal sensor readings. In this paper, we propose a novel method of detecting sensor anomalies under smart home environment by considering spatial correlation and dependable correlation between sensors. Initially, we pre-calculate these correlations of every pair of two sensors to discover their relations. Then, from periodic sensor readings, if it has any unmatched relations to the pre-computed ones, an anomaly is detected on the correlated sensor. Through extensive evaluations with real datasets, we show that the proposed method outperforms previous approaches with 20% improvement on detection rate and reasonably low false positive rate.

This paper constructs packet-oriented erasure correcting codes and their systematic forms for the distributed storage systems. The proposed codes are encoded by exclusive OR and bit-level shift operation. By the shift operation, the encoded packets are slightly longer than the source packets. This paper evaluates the extra length of the encoded packets, called overhead, and shows that the proposed codes have smaller overheads than the zigzag decodable codes, which are existing codes using bit-level shift operation and exclusive OR.

Fountain codes are erasure correcting codes realizing reliable communication systems for the multicast on the Internet. The zigzag decodable fountain (ZDF) codes are one of generalization of the Raptor codes, i.e., applying shift operation to generate the output packets. The ZDF codes are decoded by a two-stage iterative decoding algorithm, which combines the packet-wise peeling algorithm and the bit-wise peeling algorithm. By the bit-wise peeling algorithm and shift operation, ZDF codes outperform Raptor codes under iterative decoding in terms of decoding erasure rates and overheads. However, the bit-wise peeling algorithm spends long decoding time. This paper proposes fast bit-wise decoding algorithms for the ZDF codes. Simulation results show that the proposed algorithm drastically reduces the decoding time compared with the previous algorithm.

This paper provides perspectives for future medical healthcare social services and businesses that integrate advanced information and communication technology (ICT) and data science. First, we propose a universal medical healthcare platform that consists of wireless body area network (BAN), cloud network and edge computer, big data mining server and repository with machine learning. Technical aspects of the platform are discussed, including the requirements of reliability, safety and security, i.e., so-called dependability. In addition, novel technologies for satisfying the requirements are introduced. Then primary uses of the platform for personalized medicine and regulatory compliance, and its secondary uses for commercial business and sustainable operation are discussed. We are aiming at operate the universal medical healthcare platform, which is based on the principle of regulatory science, regionally and globally. In this paper, trials carried out in Kanagawa, Japan and Oulu, Finland will be revealed to illustrate a future medical healthcare social infrastructure by expanding it to Asia-Pacific, Europe and the rest of the world. We are representing the activities of Kanagawa medical device regulatory science center and a joint proposal on security in the dependable medical healthcare platform. Novel schemes of ubiquitous rehabilitation based on analyses of the training effect by remote monitoring of activities and machine learning of patient's electrocardiography (ECG) with a neural network are proposed and briefly investigated.

We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given; every pattern is composed of n lines incident to the center of a sheet of paper; every angle between adjacent lines is equal to 2π/n; every line is assigned one of “mountain,” “valley,” and “flat (or consequently unfolded)”; crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.

Peer code review is key to ensuring the absence of software defects. To reduce review costs, software developers adopt code convention checking tools that automatically identify maintainability issues in source code. However, these tools do not always address the maintainability issue for a particular project. The goal of this study is to understand how code review fixes conditional statement issues, which are the most frequent changes in software development. We conduct an empirical study to understand if-statement changes through code review. Using review requests in the Qt and OpenStack projects, we analyze changes of the if-conditional statements that are (1) requested to be reviewed, and are (2) revised through code review. We find the most frequently changed symbols are “( )”, “.”, and “!”. We also find project-specific fixing patterns for improving code readability by association rule mining. For example “!” operator is frequently replaced with a function call. These rules are useful for improving a coding convention checker tailored for the projects.

High Efficiency Video Coding (HEVC) has a better coding efficiency comparing with H.264/AVC. However, performance enhancement results in increased computational complexity which is mainly brought by the quadtree based coding tree unit (CTU). In this paper, an early termination algorithm based on AdaBoost classifier for coding unit (CU) is proposed to accelerate the process of searching the best partition for CTU. Experiment results indicate that our method can save 39% computational complexity on average at the cost of increasing Bjontegaard-Delta rate (BD-rate) by 0.18.

Modern FPGAs have been integrated in computing systems as accelerators for long running applications. This integration puts more pressure on the fault tolerance of computing systems, and the requirement for dependability becomes essential. As in the case of CPU-based system, checkpoint/restart techniques are also expected to improve the dependability of FPGA-based computing. Three issues arise in this situation: how to checkpoint and restart FPGAs, how well this checkpoint/restart model works with the checkpoint/restart model of the whole computing system, and how to build the model by a software tool. In this paper, we first present a new checkpoint/restart architecture along with a checkpointing mechanism on FPGAs. We then propose a method to capture consistent snapshots of FPGA and the rest of the computing system. Third, we provide “fine-grained” management for checkpointing to reduce performance degradation. For the host CPU, we also provide a stack which includes API functions to manage checkpoint/restart procedures on FPGAs. Fourth, we present a Python-based tool to insert checkpointing infrastructure. Experimental results show that the checkpointing architecture causes less than 10% maximum clock frequency degradation, low checkpointing latencies, small memory footprints, and small increases in power consumption, while the LUT overhead varies from 17.98% (Dijkstra) to 160.67% (Matrix Multiplication).

Protein-Protein Interaction Extraction (PPIE) from biomedical literatures is an important task in biomedical text mining and has achieved great success on public datasets. However, in real-world applications, the existing PPI extraction methods are limited to label effort. Therefore, transfer learning method is applied to reduce the cost of manual labeling. Current transfer learning methods suffer from negative transfer and lower performance. To tackle this problem, an improved TrAdaBoost algorithm is proposed, that is, relative distribution is introduced to initialize the weights of TrAdaBoost to overcome the negative transfer caused by domain differences. To make further improvement on the performance of transfer learning, an approach combining active learning with the improved TrAdaBoost is presented. The experimental results on publicly available PPI corpora show that our method outperforms TrAdaBoost and SVM when the labeled data is insufficient,and on document classification corpora, it also illustrates that the proposed approaches can achieve better performance than TrAdaBoost and TPTSVM in final, which verifies the effectiveness of our methods.

In the topologies for interconnected nodes, it is desirable to have a low degree and a small diameter. For the same number of nodes, a dual-cube topology has almost half the degree compared to a hypercube while increasing the diameter by just one. Hence, it is a promising topology for interconnection networks of massively parallel systems. We propose here a stochastic fault-tolerant routing algorithm to find a non-faulty path from a source node to a destination node in a dual-cube.

The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.

This paper proposes a fountain coding system which has lower decoding erasure rate and lower space complexity of the decoding algorithm than the Raptor coding systems. A main idea of the proposed fountain code is employing shift and exclusive OR to generate the output packets. This technique is known as the zigzag decodable code, which is efficiently decoded by the zigzag decoder. In other words, we propose a fountain code based on the zigzag decodable code in this paper. Moreover, we analyze the overhead, decoding erasure rate, decoding complexity, and asymptotic overhead of the proposed fountain code. As a result, we show that the proposed fountain code outperforms the Raptor codes in terms of the overhead and decoding erasure rate. Simulation results show that the proposed fountain coding system outperforms Raptor coding system in terms of the overhead and the space complexity of decoding.

Object detection is at the heart of nearly all the computer vision systems. Standard off-the-shelf embedded processors are hard to meet the trade-offs among performance, power consumption and flexibility required by object detection applications. Therefore, this paper presents an Application Specific Instruction set Processor (ASIP) for object detection using AdaBoost-based learning algorithm with Haar-like features as weak classifiers. Algorithm optimizations are employed to reduce memory bandwidth requirements without losing reliability. In the proposed ASIP, Single Instruction Multiple Data (SIMD) architecture is adopted for fully exploiting data-level parallelism inherent to the target algorithm. With adding pipeline stages, application-specific hardware components and custom instructions, the AdaBoost algorithm is accelerated by a factor of 13.7x compared to the optimized pure software implementation. Compared with ARM946 and TMS320C64+, our ASIP shows 32x and 7x better throughput, 10x and 224x better area efficiency, 6.8x and 18.8x better power efficiency, respectively. Furthermore, compared to hard-wired designs, evaluation results show an advantage of the proposed architecture in terms of chip area efficiency while maintain a reliable performance and achieve real-time object detection at 32fps on VGA video.

Extending the very popular tori interconnection networks[1]-[3], Torus-Connected Cycles (TCC) have been proposed as a novel network topology for massively parallel systems [5]. Here, the set-to-set disjoint paths routing problem in a TCC is solved. In a TCC(k,n), it is proved that paths of lengths at most kn2+2n can be selected in O(kn2) time.

System expandability becomes a major concern for highly parallel computers and data centers, because their number of nodes gradually increases year by year. In this context we propose a low-degree topology and its floor layout in which a cabinet or node set can be newly inserted by connecting short cables to a single existing cabinet. Our graph analysis shows that the proposed topology has low diameter, low average shortest path length and short average cable length comparable to existing topologies with the same degree. When incrementally adding nodes and cabinets to the proposed topology, its diameter and average shortest path length increase modestly. Our discrete-event simulation results show that the proposed topology provides a comparable performance to 2-D Torus for some parallel applications. The network cost and power consumption of DSN-F modestly increase when compared to the counterpart non-random topologies.

This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Möbius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n4), and the maximum path length, 2n-1. A computer experiment is conducted for n=1,2,...,31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n3) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.

Gentle AdaBoost is widely used in object detection and pattern recognition due to its efficiency and stability. To focus on instances with small margins, Gentle AdaBoost assigns larger weights to these instances during the training. However, misclassification of small-margin instances can still occur, which will cause the weights of these instances to become larger and larger. Eventually, several large-weight instances might dominate the whole data distribution, encouraging Gentle AdaBoost to choose weak hypotheses that fit only these instances in the late training phase. This phenomenon, known as “classifier distortion”, degrades the generalization error and can easily lead to overfitting since the deviation of all selected weak hypotheses is increased by the late-selected ones. To solve this problem, we propose a new variant which we call “Penalized AdaBoost”. In each iteration, our approach not only penalizes the misclassification of instances with small margins but also restrains the weight increase for instances with minimal margins. Our method performs better than Gentle AdaBoost because it avoids the “classifier distortion” effectively. Experiments show that our method achieves far lower generalization errors and a similar training speed compared with Gentle AdaBoost.