Accelerating the calculations of binary detour phase method by integrating both CUDA and Matlab programming for GPU's parallel computations

The availability of state of art GPGPU cards can play a promising role in accelerating the calculations of computer generated holograms (CGH) where one of the main problems of generating such holograms is the need for massive amount of calculations. Both CUDA and Matlab can be used alone to fulfill this purpose but using both at the same time gives a number of benefits. This paper is dedicated to present a performance study of applying Fermi-Architecture CUDA-enabled GPGPU card for speeding up the calculations of binary detour phase holograms using both Matlab and CUDA programming.     

On 2-Detour Subgraphs of the Hypercube

A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d _H (x, y) ≤ d _G (x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q _n has at least clog₂ n · 2 ⁿ edges. József Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398. Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research.     

Path extendability of claw-free graphs

Let G be a connected, locally connected, claw-free graph of order n and x,y be two vertices of G. In this paper, we prove that if for any 2-cut S of G, S∩{x,y}=∅, then each (x,y)-path of length less than n-1 in G is extendable, that is, for any path P joining x and y of length h(<n-1), there exists a path P^′ in G joining x and y such that V(P)⊂V(P^′) and |P^′|=h+1. This generalizes several related results known before.     

Geometric dilation of closed planar curves: New lower bounds

Given two points on a closed planar curve, C, we can divide the length of a shortest connecting path in C by their Euclidean distance. The supremum of these ratios, taken over all pairs of points on the curve, is called the geometric dilation of C. We provide lower bounds for the dilation of closed curves in terms of their geometric properties, and prove that the circle is the only closed curve achieving a dilation of π/2, which is the smallest dilation possible. Our main tool is a new geometric transformation technique based on the perimeter halving pairs of C.     

Study of low-energy internal Bremsstrahlung radiation from Pm

The absolute intensity of the internal Bremsstrahlung radiation following the beta decay of ¹⁴⁷Pm has been measured using a high-resolution X-ray detector in the low-energy region from 3 to 33 keV. Magnetic-deflector method has been used to avoid the betas from reaching the detector. The corrected spectral intensity has been compared with the Nilsson-corrected KUB theory. Good agreement between experiment and theory is seen in this energy region.     

A full-scale solution to the rectilinear obstacle-avoiding Steiner problem

Routing is one of the important steps in very/ultra large-scale integration (VLSI/ULSI) physical design. Rectilinear Steiner minimal tree (RSMT) construction is an essential part of routing. Macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. However, OARSMT algorithms for multi-terminal net routing still cannot meet the requirements of practical applications. This paper focuses on the OARSMT problem and gives a solution to full-scale nets based on two algorithms, namely An-OARSMan and FORSTer. (1) Based on ant colony optimization (ACO), An-OARSMan can be used for common scale nets with less than 100 terminals in a circuit. An heuristic, greedy obstacle penalty distance (OP-distance), is used in the algorithm and performed on the track graph. (2) FORSTer is a three-step heuristic used for large-scale nets with more than 100 terminals in a circuit. In Step 1, it first partitions all terminals into some subsets in the presence of obstacles. In Step 2, it then connects terminals in each connected graph with one or more trees, respectively. In Step 3, it finally connects the forest consisting of trees constructed in Step 2 into a complete Steiner tree spanning all terminals while avoiding all obstacles. (3) These two graph-based algorithms have been implemented and tested on different kinds of cases. Experimental results show that An-OARSMan can handle both convex and concave polygon obstacles with short wire length. It achieves the optimal solution in the cases with no more than seven terminals. The experimental results also show that FORSTer has short running time, which is suitable for routing large-scale nets among obstacles, even for routing a net with one thousand terminals in the presence of 100 rectangular obstacles.     

On detour homogeneous digraphs

If every vertex of a graph is an endvertex of a hamiltonian path, then the graph is called homogeneously traceable. If we require each vertex of a graph to be an endvertex of a longest path (not necessarily a hamiltonian path), then we call the graph a detour homogeneous graph. The concept of a homogeneously traceable graph was extended to digraphs by Bermond, Simões-Pereira, and C.M. Zamfirescu. Skupień introduced different classes of such digraphs. In this paper we discuss the extension of the concept of a detour homogeneous graph to digraphs.