1-6hit |
Rikuya SASAKI Hiroyuki ICHIDA Htoo Htoo Sandi KYAW Keiichi KANEKO
The increasing demand for high-performance computing in recent years has led to active research on massively parallel systems. The interconnection network in a massively parallel system interconnects hundreds of thousands of processing elements so that they can process large tasks while communicating among others. By regarding the processing elements as nodes and the links between processing elements as edges, respectively, we can discuss various problems of interconnection networks in the framework of the graph theory. Many topologies have been proposed for interconnection networks of massively parallel systems. The hypercube is a very popular topology and it has many variants. The cross-cube is such a topology, which can be obtained by adding one extra edge to each node of the hypercube. The cross-cube reduces the diameter of the hypercube, and allows cycles of odd lengths. Therefore, we focus on the cross-cube and propose an algorithm that constructs disjoint paths from a node to a set of nodes. We give a proof of correctness of the algorithm. Also, we show that the time complexity and the maximum path length of the algorithm are O(n3 log n) and 2n - 3, respectively. Moreover, we estimate that the average execution time of the algorithm is O(n2) based on a computer experiment.
Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.
Xina CHENG Norikazu IKOMA Masaaki HONDA Takeshi IKENAGA
The ball state tracking and detection technology plays a significant role in volleyball game analysis, whose performance is limited due to the challenges include: 1) the inaccurate ball trajectory; 2) multiple numbers of the ball event category; 3) the large intra-class difference of one event. With the goal of broadcasting supporting for volleyball games which requires a real time system, this paper proposes a ball state based parallel ball tracking and event detection method based on a sequential estimation method such as particle filter. This method employs a parallel process of the 3D ball tracking and the event detection so that it is friendly for real time system implementation. The 3D ball tracking process uses the same models with the past work [8]. For event detection process, a ball event change estimation based multiple system model, a past trajectory referred hit point likelihood and a court-line distance feature based event type detection are proposed. First, the multiple system model transits the ball event state, which consists the event starting time and the event type, through three models dealing with different ball motion situations in the volleyball game, such as the motion keeping and changing. The mixture of these models is decided by estimation of the ball event change estimation. Secondly, the past trajectory referred hit point likelihood avoids the processing time delay between the ball tracking and the event detection process by evaluating the probability of the ball being hit at certain time without using future ball trajectories. Third, the feature of the distance between the ball and the specific court line are extracted to detect the ball event type. Experimental results based on multi-view HDTV video sequences (2014 Inter High School Men's Volleyball Games, Japan), which contains 606 events in total, show that the detection rate reaches 88.61% while the success rate of 3D ball tracking keeps more than 99%.
Antoine BOSSARD Keiichi KANEKO
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.
Shuhei OTA Takao KAGEYAMA Mitsuhiro KIMURA
In this study, we investigate whether copula modeling contributes to the improvement of reliability evaluation in a cascading failure-occurrence environment. In particular, as a basic problem, we focus on a 2-unit parallel system whose units may fail dependently each other. As a result, the reliability assessment of the system by using the maximal copula provides more accurate evaluation than the traditional Weibull analysis, if the degree of dependency between two units are high. We show this result by using several simulation studies.
This paper discusses the asynchronous and synchronous parallel derivation of languages based on standard formal grammars. Some of the synchronous languages defined in this paper are essentially equivalent to the languages of E0L and EIL systems. Languages with restrictions on the number of parallel derivation steps are difined so that a t-time language is the set of strings w derived in t(w) or less parallel derivatio steps, where t(n) is an integer function. the properties of asynchronous derivation are generally discussed to clarify their conditions so that the derivation results are independent of the order in which productions are applied. It is shown that: (1) Any context sensitive grammar (CSG) G can be transformed into a CSG G such that the language generated by synchronous derivation in G is equal to that generated by asynchronous derivation in G , and vice versa; (2) Any regular language is a log-time context free language (CFL); (3) The class of CFLs is incomparable with that of log-time CSLs; and (4) If there is a bounded cellular automaton recognizing any language L in time T(n), then L is an O(T(n))-time CSL.