Generalized Recursive Sorting Networks

A class of recursive sorting networks based on mod(s) m-merging, a generalization of Batcher′s odd-even merging, is studied in this paper. Iterative decomposition of a sorter into smaller comparator modules, an equivalent problem but in a different setting, is also resolved based on the scheme proposed here. We first show that it is impossible to generalize the principle of odd-even merging in a three-stage network. Then the condition on generalized mod(s) m-merging with four stages is proven. This scheme degenerates to the three-stage odd-even merging network when m = 2 and s = 2. An algorithm for computing the optimal configuration is also given. Applications of this sorting network include parallel relational database computers and modular construction of sorting networks for large packet switches.     

A Bitonic Selection Algorithm on Multiprocessor System

The so-called (m, n) selection problem is defined as the selection of them smallest (or largest) numbers fromn given numbers (n>m). Solving this problem in parallel mode has been successful on the networks, but it is seldom studied on the multiprocessor systems. This paper first, based on Batcher’s principle of bitonic merging, proposes the bitonic selection network. Then it repeals the varying rule of the pivots in all successive ranks of the network through our observation to the data transfer property in the network. Finally, according to this rule, the parallel selection algorithm with running timeO (lognlogm)¹⁾ onn processors is presented. This work was supported by the National Science Foundation of China under Grant Tech.-85217.     

Single-exception sorting networks and the computational complexity of optimal sorting network verification

Asorting network is a combinational circuit for sorting constructed from comparison-swap units. The depth of such a circuit is a measure of its running time. It is known that sorting-network verification is computationally intractable. However, it is reasonable to hypothesize that only the fastest (that is, the shallowest) networks are likely to be fabricated. It is shown that the verification of shallow sorting networks is also computationally intractable. Firstly, a method for constructing asymptotically optimalsingle-exception sorting networks is demonstrated. These are networks which sort all zero-one inputs except one. More specifically, their depth isD(n-1)+2log(n-1)+2, whereD(n) is the minimum depth of ann-input sorting network. It follows that the verification problem for sorting networks of depth 2D(n)+6logn+O(1) is Co-NP complete. Given the current state of knowledge aboutD(n) for largen, this indicates that the complexity of verification for shallow sorting networks is as great as for deep networks.This research was supported by NSF Grant CCR-8801659.     

All-to-All Optical Routing in Chordal Rings of Degree 4

We consider the problem of routing in networks employing all-optical routing technology. In such networks, information between nodes of the network is transmitted as light on fiber-optic lines without being converted to electronic form in between. We consider switched optical networks that use the wavelength-division multiplexing (or WDM) approach. A WDM network consists of nodes connected by point-to-point fiber-optic links, each of which can support a fixed number of wavelengths. The switches are capable of redirecting incoming streams based on wavelengths, without changing the wavelengths. Different messages may use the same link concurrently if they are assigned distinct wavelengths. However, messages assigned the same wavelength must be assigned edge-disjoint paths. Given a communication instance in a network, the optical routing problem is the assignment of {routes} to communication requests of the instance, as well as wavelengths to routes so that the number of wavelengths used by the instance is minimal. We focus on the all-to-all communication instance I _A in a widely studied family of chordal rings of degree 4, called optimal chordal rings . For these networks, we prove exact bounds on the optimal load induced on an edge for I _A , over all shortest-path routing schemes. We show an approximation algorithm that solves the optical routing problem for I _A using at most 1.006 times the lower bound on the number of wavelengths. The previous best approximation algorithm has a performance ratio of 8. Furthermore, we use a variety of novel techniques to achieve this result, which are applicable to other communication instances and may be applicable to other networks. Received July 22, 1998; revised October 14, 1999.     

结合全卷积网络与CycleGAN的图像实例风格迁移

目的 传统的图像风格迁移主要在两个配对的图像间进行。循环一致性对抗网络（CycleGAN）首次将生成对抗网络应用于图像风格迁移,实现无配对图像之间的风格迁移,取得了一定的效果,但泛化能力较弱,当训练图像与测试图像之间差距较大时,迁移效果不佳。针对上述问题,本文提出了一种结合全卷积网络（FCN）与CycleGAN的图像风格迁移方法,使得图像能够实现特定目标之间的实例风格迁移。同时验证了训练数据集并非是造成CycleGAN风格迁移效果不佳的因素。方法 首先结合全卷积网络对图像进行语义分割,确定风格迁移的目标,然后将风格迁移后的图像与目标进行匹配,确定迁移对象实现局部风格迁移。为验证CycleGAN在训练图像和测试图像差距较大时风格转移效果不佳并非因缺少相应训练集,制作了训练数据集并带入原网络训练。结果 实验表明结合了全卷积网络与CycleGAN的图像风格迁移方法增加了识别能力,能够做到图像局部风格迁移而保持其余元素的完整性,相对于CycleGAN,该方法能够有效抑制目标之外区域的风格迁移,实验中所用4张图片平均只有4.03%的背景像素点发生了改变,实例迁移效果得到很好提升。而将自制训练集带入原网络训练后,依然不能准确地在目标对象之间进行风格迁移。结论 结合了全卷积网络与CycleGAN的方法能够实现图像的局部风格迁移而保持目标对象之外元素不发生改变,而改变训练数据集对CycleGAN进行实例风格迁移准确性的影响并不大。     

Sorting and Counting Networks of Arbitrary Width and Small Depth

We present the first construction for sorting and counting networks of arbitrary width that requires both small depth and small constant factors in the depth expression. Let w be the product w = p ₀ ⋅ p ₁ ⋅s p _n-1 , whose factors are not necessarily prime. We present a novel network construction of width w and depth O(n ² ) = O(log ² w) , using comparators (or balancers) of width less than or equal to max(p _i ) . This construction is practical in the sense that the asymptotic notation does not hide any large constants. An interesting aspect of this construction is that it establishes a family of sorting and counting networks of width w , one for each distinct factorization of w . A factorization in which max(p _i ) is large and n is small yields a network that trades small depth for large comparators (or balancers), and a factorization where max(p _i ) is small and n is large makes the opposite tradeoff. Received June 18, 2001. Online publication October 30, 2001.     

A three-step decomposition method for the evolutionary design of sequential logic circuits

Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate the configurations of the programmable devices. The scalability is one of the main obstacles preventing EHW from being applied to real-world applications. Several techniques have been proposed to overcome the scalability problem. One of them is to decompose the whole circuit into several small evolvable sub-circuits. However, current techniques for scalability are mainly used to evolve combinational logic circuits. In this paper, in order to decompose a sequential logic circuit, the state decomposition, output decomposition and input decomposition are united as a three-step decomposition method (3SD). A novel extrinsic EHW system, namely 3SD–ES, which combines the 3SD method with the (μ, λ) ES (evolution strategy), is proposed, and is used for the evolutionary designing of larger sequential logic circuits. The proposed extrinsic EHW system is tested extensively on sequential logic circuits taken from the Microelectronics Center of North Carolina (MCNC) benchmark library. The results demonstrate that 3SD–ES has much better performance in terms of scalability. It enables the evolutionary designing of larger sequential circuits than have ever been evolved before.     

The New Class of g-Chain Periodic Sorters

Aperiodic sorteris a sorting network that is a cascade of a number of identicalblocks, where outputiof each block is inputiof the next block. Previously, Dowd, Perl, Rudolph, and Saks introduced thebalancedmerging network, withN=2^kinputs/outputs and log Nstages of comparators. Using a very intricate proof, they showed that a cascade of log Nsuch blocks constitutes a sorting network. In this paper, we introduce a large class of merging networks with the same periodic property. This class contains 2^N/2−1networks, whereN=2^kis the number of inputs. The balanced merger is one network in this class. Other networks use fewer comparators. We provide a very simple and elegant correctness proof based on the recursive structure of the networks.     

A Superlogarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks

Shuffle-unshuffle sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n -input shuffle-unshuffle sorting networks with depth have been discovered. These networks are the only known sorting networks of depth o( lg ² n) that are not based on expanders, and their existence raises the question of whether a depth of O( lg n) can be achieved by any shuffle-unshuffle sorting network. In this paper we resolve this question by establishing an Ω( lg n lg lg n/lg lg lg n) lower bound on the depth of any n -input shuffle-unshuffle sorting network. Our lower bound can be extended to certain restricted classes of nonoblivious sorting algorithms on hypercubic machines. Received September 9, 1999, and in final form December 20, 1999.     

QRTP: A Middleware for Broadband Networks

Broadband networks, such as those based on Asynchronous Transfer Mode (ATM), provide large bandwidth and multiple services. An essential application area for broadband networks is multimedia systems. The development of multimedia applications, however, is currently lagging behind the advances in the network technology. Our approach to the problem of more effectively developing multimedia applications is to provide developers with a middleware that encompasses a set of broadband-specific services needed by multimedia applications, for instance virtual connection setup, bandwidth reservation and session synchronization. Our middleware, called the Queen's Real-time Transport Protocol (QRTP), is based on the Real-time Transport Protocol standard from the Internet Engineering Task Force. The paper discuses the design, implementation and evaluation of the QRTP middleware.     

RanGen: A Random Network Generator for Activity-on-the-Node Networks

In this paper, we describe RanGen, a random network generator for generating activity-on-the-node networks and accompanying data for different classes of project scheduling problems. The objective is to construct random networks which satisfy preset values of the parameters used to control the hardness of a problem instance. Both parameters which are related to the network topology and resource-related parameters are implemented. The network generator meets the shortcomings of former network generators since it employs a wide range of different parameters which have been shown to serve as possible predictors of the hardness of different project scheduling problems. Some of them have been implemented in former network generators while others have not.     

Sorting Unsigned Permutations by Weighted Reversals,Transpositions, and Transreversals

Reversals, transpositions and transreversals are common events in genome rearrangement. The genome rearrangement sorting problem is to transform one genome into another using the minimum number of given rearrangement operations. An integer permutation is used to represent a genome in many cases. It can be divided into disjoint strips with each strip denoting a block of consecutive integers. A singleton is a strip of one integer. And the genome rearrangement problem turns into the problem of sorting a permutation into the identity permutation equivalently. Hannenhalli and Pevzner designed a polynomial time algorithm for the unsigned reversal sorting problem on those permutations with O(log n) singletons. In this paper, first we describe one case in which Hannenhalli and Pevzner’s algorithm may fail and propose a corrected approach. In addition, we propose a (1+ε)-approximation algorithm for sorting unsigned permutations with O(log n) singletons by reversals of weight 1 and transpositions/transreversals of weight 2.     

A Partitioning Selection Algorithm on Multiprocessors

The so-called(m,n)selection problem is the problem of selecting the m smallest(orlargest)elements from n given numbers(n>m).With the development of parallel computers,much attention has been paid to the design of efficient algorithms of(m,n)problem for thesemachines.The parallel selection algorithm has been successful on networks,but seldom studiedon the multiprocessing systems.This paper,based on a partitioning approach,proposes apartitioning algorithm of selection on multiprocessors using Valiant's merging and sortingschemes.By means of this algorithm,(m,n)selection problem can be completed in parallel n/2processors in time O(loguloglogm-log(n/m)loglog(n/m)).     

Discovering timely information in MANETs

Timely information refers to information whose ‘most recent’ or ‘latest’ instance is most valuable. In mobile ad hoc networks (MANETs), multiple instances of a piece of timely information may be produced by different nodes at different points in time. The problem is to discover the ‘latest’ instance among all existing instances. Within the context of MANETs, timely information discovery is fundamentally different from the existing resource/service discovery problem whose goal is to discover either any instance or a subset of instances which satisfy a local query constraint that can be specified and evaluated using only local attributes of each individual node. In contrast, the timely information discovery problem imposes the global (timeliness) constraint which should best be evaluated when all the instances are considered to determine the latest instance. The complication of discovering timely information arises from the existence of multiple instances of the information, which are produced at different points in time by different nodes in the network, and the need to collect all these instances to decide the latest instance. For MANETs, the lack of infrastructure supports, frequent topology changes, and potential packet loss in wireless communications further challenge the problem of timely information discovery. This paper describes a self-organizing, peer-to-peer based approach, termed ALADIN, to discovering timely information in MANETs. In ALADIN, nodes that produce instances of the timely information are peers who self-organize an adaptive and distributed ‘search infrastructure’ to facilitate the discovery of the latest instance. A simulation study shows that ALADIN is scalable without incurring network-wide flooding in the case of large-scale networks and popular timely information, and yields a high chance of discovering the latest instance in the presence of mobility.     

Single-layer cylindrical compaction

In VLSI compaction, an array composed of a single cell warrants special consideration. Standard methods of compaction [MS] result in either nonuniform cell layouts or unnecessarily large cell spacing. These inadequacies would be lessened were the array compacted instead by compacting a single instance of the cell against itself: in essence, the cell would be compacted on a torus. Equivalently, the problem becomes that of compacting a layout to fit into a minimal area shape 4-tiling the plane.Only the one-dimensional version of the problem has been addressed: that equivalent to compaction on a cylinder. Unfortunately, the efficient longest-path approach to one-dimensional compaction is not directly applicable since there is no origin to compact against. Eichenberger and Horowitz solve the problem in polynomial time by using a min-cost flow approach to assign positions to the nodes of a constraint network embedded on a cylinder [EH]. Mehlhorn and Rülling found an iterative approach running in timeO(n ² logn) when restricted to networks abstracted from layouts having any fixed number of layers [MR]. In this paper the longest-path approach is adapted to solve the same cylindrical compaction problem on planar networks—those abstracted from single-layer layouts—in justO(n logn) time.This research was supported by NSF Presidential Young Investigator Grant MIP-8657693.     

Efficient Parallel Matrix Inversion on Interconnection Networks

In this paper, we present efficient algorithms for the inversion of a triangular matrix on different interconnection networks. For hypercubes, we describe an elegant straightforward implementation of L. Csansky's well known PRAM algorithm [Ph.D. dissertation, Computer Sci. Div., Univ. of California, Berkeley 1974]. The time complexity is (log²n) usingn³processors, i.e., within the same order as the PRAM algorithm. Moreover, we give a general approach for the design of triangular matrix inversion algorithms on a large class of networks. Applied to some of these networks, as, e.g., the de Bruijn network, the shuffle-exchange network, and the cube-connected-cycles, this approach yields triangular matrix inversion algorithms that meet the PRAM complexity bounds of the problem within a small constant.     

A generalization of the 0-1 principle for sorting

The traditional zero-one principle for sorting networks states that “if a network with n input lines sorts alln² binary sequences into nondecreasing order, then it will sort any arbitrary sequence of n numbers into nondecreasing order”. We generalize this to the situation when a network sorts almost all binary sequences and relate it to the behavior of the sorting network on arbitrary inputs. We also present an application to mesh sorting.     

Automated Delineation of Subgroups in Web Video: A Medical Activism Case Study

Web 2.0 tools in general, and Web video in particular, provide new ways for activists to express their viewpoints to a broad audience. In this paper we deployed tools that have been used to find subgroups automatically in social networks and applied them to the problem of distinguishing between two sides of a controversial issue based on patterns of online interaction. We explored the problem of distinguishing between anti‐ and pro‐vaccination activists based on a social network of videos and associated comments posted on YouTube. Videos for the analysis were selected by submitting the term “vaccination” to a search on YouTube. A content analysis of the selected videos was then performed ( Keelan et al, 2007 ) to classify videos as pro‐ or anti‐vaccination. Then, a modified version of the SCAN method ( Chin and Chignell, 2008 ) for identifying cohesive subgroups in social networks was applied to the social network inferred from the discussions about the videos. Results showed that a cohesive subgroup of anti‐vaccination people existed in discussions around anti‐vaccination videos, whereas discussions around pro‐vaccination videos included both anti‐vaccination and pro‐vaccination people. Implications of the method and results for more general delineation of types of medical activism and the opposing camps within those camps are discussed.     

Periodic Merging Networks

We consider the problem of merging two sorted sequences on constant degree networks performing compare—exchange operations only. The classical solution to this problem is given by the networks based on Batcher's Odd—Even Merge and Bitonic Merge running in log(2n ) time. Due to the obvious log n lower bound for the runtime, this is time-optimal. We present a new family of merging networks working in a completely different way than the previously known algorithms. They have a novel property of being periodic: this means that for some (small) constant k , each processing unit of the network performs the same operations at steps t and t+k (as long as t+k does not exceed the runtime). The only operations executed are compare—exchange operations, just like in the case of Batcher's networks. The architecture of the networks is very simple and easy to lay out. We show that even for period 3 there is a network in our family merging two n -element sorted sequences in time O(log n ). Since each network of period 2 requires steps to merge such sequences, 3 is the smallest period for which we may achieve a fast runtime. In order to improve constants standing in front of log n we increment the period and tune the construction using additional techniques. We achieve the runtime 9 . . . log_3 n 5.7 . . . log n for a network of period 4, and 2.25 . . . ((k+3)/(k-1+log 3))log n 2.25 . . . log n for a network of period k+3 , for . Due to the periodic design, our networks have small area complexity. For instance, if each processing unit requires O(1) area and a comparator uses a single wire of width O(1) connecting the processing elements, then our networks require area. This compares well with Batcher's networks that require area . Received February 1997, and in revised form September 1997, and in final form February 1998.     

An Approximation Algorithm for Circular Arc Colouring

We consider the problem of colouring a family of n arcs of a circle. This NP-complete problem, which occurs in routing and network design problems, is modelled as a 0-1 integer multicommodity flow problem. We present an algorithm that routes the commodities in the network by augmenting the network with some extra edges which correspond to extra colours. The algorithm, which relies on probabilistic techniques such as randomized rounding and path selection, is a randomized approximation algorithm which has an asymptotic performance ratio of 1+1/e (approximately 1.37) except when the minimum number of colours required is very small (O(\ln n) ). This is an improvement over the best previously known result [7], which is a deterministic approximation algorithm with a performance ratio of 3/2. The substantial improvement is valuable, for instance in wavelength allocation strategies in communication networks where bandwidth is a precious resource. Received October 25, 1998; revised August 26, 1999, and April 17, 2000.