bluuebunny/crossref_metadata_2025 huggingface dataset:
Big old cottonwoods
Authors: Rood Stewart B , Polzin Mary Louise
Published: September 2003

In studying riparian woodlands along streams across western North America, we observed a grove of exceptionally large and old black cottonwoods, Populus trichocarpa Torr. & A. Gray, along the Elk River in southeastern British Columbia. Situated in a floodplain forest dominated by western red cedar, Thuja plicata Donn ex D. Don, the cottonwoods were up to 2.2 m in diameter, and although heart rot prevented precise aging, increment cores indicated ages of up to 400 years. This demonstrated the potential for substantial longevity of section Tacamahaca cottonwoods (including Populus angustifolia James and Populus balsamifera L.) compared with section Aigeiros species (Populus deltoides Bartr. and Populus fremontii Wats.), which are shorter lived (about 150 year maximum). Very old cottonwoods make distinctive contributions to habitat structure of riparian woodlands and reveal stable floodplain locations that have not been eroded by the river channel for the duration of the trees' lives.Key words: aging, poplars, riparian, trees.
Taxonomic aspects of Peronosporaceae inferred from Bayesian molecular phylogenetics
Authors: Göker M , Voglmayr H , Riethmüller A , Weiß M , Oberwinkler F
Published: September 2003

We present the results of a Bayesian phylogenetic analysis of parts of the nuclear 28S rDNA of a representative sample of the Peronosporales. Peronospora s.l. is shown to be paraphyletic. Based on molecular and morphological evidence, several species of the genus Peronospora are transferred to Hyaloperonospora. Plasmopara oplismeni appears to be related only distantly to the other Plasmopara species, and is transferred to the new genus Viennotia based on molecular, morphological, and ecological evidence. The remaining Plasmopara species are likely to be paraphyletic with respect to Bremia, Paraperonospora, and Basidiophora. Phytophthora is shown to be paraphyletic with respect to the obligatory biotrophic genera. Evidence for the assumption that obligatory biotrophism arose independently at least twice in Peronosporales is demonstrated.Key words: LSU rDNA, Straminipila, Peronosporomycetes, Peronosporales, downy mildews, Bayesian phylogenetic analysis.
New information onLethiscus stocki(Tetrapoda: Lepospondyli: Aistopoda) from high-resolution computed tomography and a phylogenetic analysis of Aistopoda
Authors: Anderson Jason S , Carroll Robert L , Rowe Timothy B
Published: September 2003

High-resolution computed tomography provides an alternative to serial sectioning and other destructive techniques of studying fossils (data available at http://www.DigiMorph.org). This technology was used to study the oldest aistopod Lethiscus stocki. The fossil is found to have approximately 30 closely spaced teeth on its maxilla and dentary, a short vomer, a palatine running nearly the entire length of the maxilla that is toothed at least posteriorly, and a choana that is located at the premaxillamaxilla suture. It has a lower jaw with a high articlular facet for the quadrate condyle; a lateral fossa for the adductor musculature, superficially similar to the mammalian masseteric fossa; and a sutural pattern that closely resembles that of Oestocephalus. Previously reported pectoral elements are not evident in the scans and may be best interpreted as fractures on the surface of the nodule associated with sedimentary inclusions. Relationships among all relatively complete aistopods were analyzed using parsimony. Two most parsimonious trees were found, differing in the arrangement of the outgroup taxa. Phlegethontia and Pseudophlegethontia are found to be sister taxa to Coloraderpeton and Oestocephalus, with Ophiderpeton and Lethiscus placed as successively more distant taxa. This topology renders Ophiderpetontidae, as previously conceived, paraphyletic. Lethiscus is confirmed to be the most basal aistopod. A new classification of Aistopoda is presented. This study shows that the palatoquadrate of higher aistopods is derived in-group, which is consistent with the trends in aistopods of peramorphosis in the endochondral skeleton and paedomorphosis in the dermal skeleton.
Thermal annealing of fission tracks in fluorapatite, chlorapatite, manganoanapatite, and Durango apatite: experimental results
Authors: Ravenhurst Casey E , Roden-Tice Mary K , Miller Donald S
Published: September 2003

It is well known that the optically measured lengths of fission tracks in apatite crystals are a function of etching conditions, crystallographic orientation of the track, composition of the crystal, and the state of thermal annealing. In this study we standardize etching conditions and optimize track length measurability by etching until etch pits formed at the surface of each apatite crystal reached widths of about 0.74 μm. Etching times using 5M HNO3 at 21°C were 31 s for Otter Lake, Quebec, fluorapatite; 47 s for Durango, Mexico, apatite; 33 s for Portland, Connecticut, manganoanapatite; and 11 s for Bamle, Norway, chlorapatite. An etching experiment using two etchant strengths (5M and 1.6M HNO3) revealed that, despite significant differences in etch pit shape, fission-track length anisotropy with respect to crystallographic orientation of the tracks is not a chemical etching effect. A series of 227 constant-temperature annealing experiments were carried out on nuclear reactor induced tracks in oriented slices of the apatites. After etching, crystallographic orientations of tracks were measured along with their lengths. The 200300 track lengths measured for each slice were ellipse-fitted to give the major (c crystallographic direction) and minor (a crystallographic direction) semi-axes used to calculate equivalent isotropic lengths. The equivalent isotropic length is more useful than mean length for thermal history analysis because the variation caused by anisotropy has been removed. Using normalized etching procedures and equivalent isotropic length data, we found that the fluorapatite anneals most readily, followed by Durango apatite, manganoanapatite, and lastly chlorapatite.
Thermochronology of the Needle Falls Shear Zone: a post-collisional high-strain zone of the Trans-Hudson Orogen
Authors: Fedorowich John S , Stauffer Mel R , Kerrich Rob , Lewry John F
Published: September 2003

The Needle Falls Shear Zone is a major Paleoproterozoic discontinuity separating an Archean craton from accreted Paleoproterozoic terranes in the western Trans-Hudson Orogen. It is a 1 km-wide subvertical mylonite zone forming the southwestern sector of a northeast-trending shear system extending for more than 400 km. Kinematic data indicate oblique, east-side-up dextral strike-slip displacement throughout its evolution from ductile through late brittle deformation. For most of its exposed length, it marks the northwestern margin of the Wathaman Batholith. The oldest Pb-evaporation ages of zircons from mylonite average 1857 Ma, consistent with published zircon ages of the Wathaman Batholith, confirming the batholith is protolith for much of the shear zone. The synkinematic metamorphic assemblage of amphibolebiotitequartzfeldspar signifies deformation under amphibolite-facies conditions (500630°C). Oxygen isotope fractionations between quartzhornblende and quartzbiotite pairs in textural equilibrium give temperatures from 430°C to 610°C, with a mode at 550°C. For hornblendebiotite pairs, 40Ar/39Ar plateau ages of hornblende cluster at 1780 Ma and of biotite at 1757 Ma. Given textural and oxygen isotope equilibrium between hornblende, biotite, and quartz, these ages are interpreted as cooling ages; consequently, this sector of the Trans-Hudson Orogen cooled from 500°C to 300350°C over about 23 million years following ductile deformation. The timing of ductile deformation cannot be well constrained, but occurred after emplacement of the Wathaman Batholith at 1857 Ma and prior to cooling of amphibole below its Ar blocking temperature at 1780 Ma.
Contractional uplift of deep crustal rocks along the Legs Lake shear zone, western Churchill Province, Canadian Shield
Authors: Mahan Kevin H , Williams Michael L , Baldwin Julia A
Published: September 2003

The Legs Lake shear zone juxtaposes high-pressure (1.0+ GPa) granulite- and eclogite-facies rocks with low-pressure (~0.5 GPa) amphibolite- to granulite-facies rocks, and thus may represent an important crustal-scale, exhumation-related structure in the western Canadian Shield. Field mapping and structural and petrologic analysis document the deformation and metamorphic history of rocks within and adjacent to the shear zone. At least two important phases of deformation are recorded: (1) early oblique thrusting (D2) that placed high-grade rocks over lower grade rocks, and (2) more discrete and lower grade brittleductile normal faulting (D3) that may represent the later part of the exhumation history. The northwest-dipping shear zone consists of 58 km of mylonite in map view, which bounds the southeast margin of the East Athabasca mylonite triangle. High-pressure granulite-facies metamorphism (~750850 °C, 1.01.2 GPa) occurred in the East Athabasca mylonite triangle at ca. 1900 Ma, prior to D2 juxtaposition with the adjacent low-pressure Hearne domain. Thermobarometry from GrtCrdSilBtQtz metapelites in the Hearne domain suggests peak conditions reached 600700 °C and 0.450.5 GPa, which are interpreted to have occurred late during D2. Published and preliminary UPb isotope dilution - thermal ionization mass spectrometry (ID-TIMS) zircon geochronology and electron microprobe monazite geochronology suggest that deformation in the Legs Lake shear zone coincided with the ca. 18301810 Ma terminal collision in the Trans-Hudson orogeny. Extensional faulting during D3 most likely occurred after ca. 1780 Ma. A multi-stage process of exhumation involving both thrust and normal-sense shearing, may serve as a model for the exhumation of other regionally extensive deep-crustal exposures.
Application of seismic stratigraphy and sedimentology to regional hydrogeological investigations: an example from Oak Ridges Moraine, southern Ontario, Canada
Authors: Sharpe D R , Pugin A , Pullan S E , Gorrell G
Published: September 2003

Hydrogeological models need to be supported by a clear understanding of the subsurface geology to provide effective assessment, flow modelling, or management of groundwater regimes. This paper illustrates how geophysical and sedimentological data can be used to significantly improve watershed-scale hydrostratigraphic models by advancing our understanding of the subsurface through regional hydrogeological investigations in the Greater Toronto Area. The example of a 3 km shallow seismic reflection survey that traverses a buried channel within Bowmanville Creek watershed, Oak Ridges Moraine, Ontario, illustrates a basis for linking geophysical and sedimentological properties to regional hydrostratigraphic parameters. Seismic reflection methods plus seismic stratigraphy and a well-constrained three-dimensional geological framework have helped to (i) identify regional hydrostratigraphic units, (ii) define properties and trends of these unitsfacies, (iii) improve depositional models that assist hydrogeological analysis, and (iv) establish a hydrostratigraphic framework within a watershed. The extent, proportions, boundaries, and variation in internal properties of major hydrostratigraphic units could be identified to greater than 100 m depth. Geostatistical analysis of seismic amplitudes was used to provide a quantitative measure of heterogeneity in a glaciofluvial aquifer with inadequate parameter support. Benefits to engineering practice include improved siting of monitors and tests from portrayal of the spatial organization, geometry, and variability of hydrostratigraphic units based on sedimentary architecture and environments of deposition. Hydrogeological modelling can be improved with better knowledge of the geometry of aquifers and aquitards and grid-cell boundaries that correspond with the defined sediment boundaries that control properties.Key words: Oak Ridges Moraine, hydrogeology, seismic stratigraphy, southern Ontario, sedimentology.
Difference between current and voltage measurements in resonant-column testing
Authors: Cascante Giovanni , Vanderkooy John , Chung Wilson
Published: September 2003

The resonant-column test is one of the most common procedures for dynamic characterization of soils (American Society for Testing and Materials standard). The test procedures require the measurement of the current flowing through the driving coils. In many cases, however, the input voltage has been measured and the results analyzed as a traditional current measurement. In this paper, the difference between current and voltage measurements is clarified; specifically, a new transfer function is presented for the analysis of data when the input voltage is measured. The new model is evaluated by testing three aluminum probes. Wave velocities computed from voltage and current measurements are similar; however, damping ratios are significantly overestimated if voltage-based measurements are analyzed with the standard procedures because the motion of the magnets induces an opposite voltage in the coils. Results from voltage and current measurements agree only if the new transfer function is used for the analysis of voltage data. Exploratory results for a dry-sand specimen, tested under different shear-strain levels (maximum shear strain γmax< 103), demonstrate the effect of nonlinear behaviour on current and voltage measurements. Current-based measurements are recommended because they do not require the evaluation of the complex impedance of the driving coils. Furthermore, current-based measurements are more precise, especially for the characterization of specimens that have low resonant frequencies.Key words: resonant-column testing, damping ratio, attenuation, mechanical waves, shear modulus, wave velocity.
Numerical analysis of seismically induced liquefaction in earth embankment foundations. Part II. Application of remedial measures
Authors: Adalier Korhan , Aydingun Ogun
Published: September 2003

In Part I, a benchmark model without any liquefaction remediation countermeasure was considered and numerical results were compared with centrifuge experiment results. In Part II, three additional models with remediation are analyzed and compared with centrifuge experiments conducted on identical models. The countermeasures considered are densification of the sand layer by compaction, gravel berm surcharge, and sheet pile enclosure. In addition to comparing numerical results with experimental data for each model, the effect of each countermeasure relative to the benchmark model is also discussed. Insights into the dynamic behavior of the employed embankmentfoundation and liquefaction countermeasure systems are provided. The results of this study show that computer simulation of earthquake effects on embankments with liquefiable foundations with and without several different retrofit measures is possible using data from conventional laboratory tests and a verified numerical procedure.Key words: liquefaction countermeasures, numerical modeling, coupled formulation, centrifuge, embankment, earthquakes.
The application of dynamic programming to slope stability analysis
Authors: Pham Ha T.V , Fredlund Delwyn G
Published: September 2003

The applicability of the dynamic programming method to two-dimensional slope stability analyses is studied. The critical slip surface is defined as the slip surface that yields the minimum value of an optimal function. The only assumption regarding the shape of the critical slip surface is that the surface is an assemblage of linear segments. Stresses acting along the critical slip surface are computed using a finite element stress analysis. Assumptions associated with limit equilibrium methods of slices related to the shape of the critical slip surface and the relationship between interslice forces are no longer required. A computer program named DYNPROG was developed based on the proposed analytical procedure, and numerous example problems have been analyzed. Results obtained when using DYNPROG were compared with those obtained when using several well-known limit equilibrium methods. The comparisons demonstrate that the dynamic programming method provides a superior solution when compared with conventional limit equilibrium methods. Analyses conducted also show that factors of safety computed when using the dynamic programming method are generally slightly lower than those computed using conventional limit equilibrium methods of slices; however, as Poisson's ratio approaches 0.5, the computed factors of safety from the dynamic programming method and the limit equilibrium method appear to become similar.Key words: dynamic programming, slope stability, stress analysis, optimization theory, limit equilibrium methods of slices.
Cyclic hydroxamates, especially multiply substituted [1,2]oxazinan-3-ones
Authors: Wolfe Saul , Wilson Marie-Claire , Cheng Ming-Huei , Shustov Gennady V , Akuche Christiana I
Published: September 2003

Routes to putative N-acyl-D-ala-D-ala surrogates, beginning with the conversion of 4-, 5-, and 6-membered lactones into 5-, 6-, and 7-membered cyclic hydroxamates, are reported. The key step of the synthesis is trimethylaluminium-promoted cyclization of an ω-aminooxyester. The 7-membered cyclic hydroxamate crystallizes in a chair conformation. Extension of the reaction sequence to homoserine or homoserine lactone leads to cyclocanaline and N-acylated cyclocanalines. The 4-phenylacetamido derivative of cyclocanaline crystallizes in a boat conformation. The attachment of a 2-carboxypropyl substituent to the ring nitrogen of a 4-acylaminocyclocanaline has been effected, prior to cyclization, by coupling of the acyclic aminooxyester precursor to the triflate of benzyl lactate or, after cyclization, by coupling to tert-butyl α-bromopropionate in the presence of potassium fluoride  alumina, followed by removal of the protecting group in each case. A six-membered homolog of the antibiotic lactivicin has been synthesized by the reaction of 4-phenylacetamidocyclocanaline with benzyl 2-oxoglutarate in the presence of carbodiimide, followed by hydrogenolysis. Starting with methyl 2,4-dibromo-2,4-dideoxy-L-erythronate, which is available in two steps from L-ascorbic acid, these reaction sequences have been applied to the stereospecific synthesis of a D-alanine derivative whose nitrogen atom is enclosed within a 3,4-disubstituted [1,2]oxazinan-3-one. Key words: D-ala-D-ala surrogate, cyclocanaline, homolactivicin, peptidoglycan, trimethylaluminium.
A Note on Limited Preemption
Authors: Coffman E. G. , Even S.
Published: September 2003

The concept of limited preemption is introduced, where a task can be preempted, but can not be moved from one processor to another. For optimal makespan scheduling on two processors, the worst case ratio of the makespan with no preemption to that with limited preemption is shown to be 4/3, while the worst case ratio of the makespan with limited preemption to that with unlimited preemption is 4/3 as well.
Optimal Time Self-Stabilization in Uniform Dynamic Systems
Authors: Dolev Shlomi
Published: September 2003

In this paper we present a randomized uniform self-stabilizing protocol that provides each (anonymous) processor of a uniform system with a distinct identifier. The protocol uses a predefined fixed amount of memory and stabilizes within expected Θ(d) time, where d is the actual diameter of the network. The naming protocol can be combined with self-stabilizing protocols that assume distinct identifiers for the processors. Thus, we achieve with optimal time and predefined amount of memory uniform self-stabilizing protocols for many tasks including: Spanning tree construction, leader election and reset.
Parallel Algorithms for Listing Well-Formed Parentheses Strings
Authors: Vajnovszki Vincent , Pallo Jean
Published: September 2003

We present two cost-optimal parallel algorithms generating the set of all well-formed parentheses strings of length 2n with constant delay for each generated string. In our first algorithm we generate in lexicographic order well-formed parentheses strings represented by bitstrings, and in the second one we use the representation by weight sequences. In both cases the computational model is based on an architecture CREW PRAM, where each processor performs the same algorithm simultaneously on a different set of data. Different processors can access the shared memory at the same time to read different data in the same or different memory locations, but no two processors are allowed to write into the same memory location simultaneously. These results complete a recent parallel generating algorithm for well-formed parentheses strings in a linear array of processors model, due to Akl and Stojmenović.
Efficient Parallel Sparse Triangular Solution Using Selective Inversion
Authors: Raghavan Padma
Published: September 2003

In a fully parallel sparse direct solver the matrix factors are first computed and then used in forward and back substitution steps to compute the solution. On message passing multiprocessors these substitution steps are not performed at high efficiency and pose a performance bottleneck for applications in which many systems with the same matrix are solved. We present a "selective inversion" scheme (SI) which computes inverses of a sequence of submatrices of the factor and uses these to replace substitution steps by more efficient distributed matrix-vector multiplications. Experiments on the Intel Paragon and the IBM-SP2 demonstrate that the scheme has ideal scaled efficiency for 1 – 128 processors and is significantly faster than the traditional approach. The cost of selective inversion is a small fraction of the factorization cost; it is approximately 6% of the factorization cost for the model, two and three dimensional five-point, finite-difference grids. On message-passing multiprocessors with high communication latency, the extra inversion cost is easily offset by reduced triangular solution time even for a relatively small number of right-hand-side vectors.
Implementing Parallel Branch-and-Bound with Extended Sisal 2.0
Authors: Chen Yung-Syau , Gaudiot Jean-Luc
Published: September 2003

Parallel branch-and-bound is an optimization technique which renders more efficient the solution of some hard problems such as the puzzle of colored blocks and the traveling-salesman problem. In a functional language such as Sisal 2.0, it is difficult for the programmer to describe a parallel version of this technique due to the lack of imperative features in the language. In this paper, we propose a version of Sisal 2.0 extended with user-declared mutable global variables in order to enable Sisal programmers to apply the parallel branch-and-bound technique. In a simple example (the puzzle of colored blocks), we show that this approach yields better performance than either conventional functional programs or imperative programs. It is easy to see that the same strategy can be used to solve a number of hard problems such as the traveling-salesman problem.
From the Modeling of Parallel Relational Query Processing to Query Optimization and Simulation
Authors: Brunie Lionel , Kosch Harald , Wohner Wolfgang
Published: September 2003

This paper presents a novel theoretical model for representing parallel relational query processing. It is based on two components. First, a scheme graph, called DPL graph, describes all possible execution dependencies between operators, including communication and run-time control mechanisms. Second, a timed high-level Petri net is used for modeling the data- and control flow of DPL graphs. Our model provides the framework for implementing a parallel query optimizer which is able to access sub-search spaces not yet considered. Furthermore, based on the DPL graphs and its related timed high-level Petri net, a simulation environment has been designed for testing run-time control strategies as well as query optimization methods.
Parallel Image Processing Using Neural Networks: Applications in Contrast Enhancement of Medical Images
Authors: Mattes J. , Trystram D. , Demongeot J.
Published: September 2003

This paper describes the implementation of a parallel image processing algorithm, the aim of which is to give good contrast enhancement in real time, especially on the boundaries of an object of interest defined by a grey homogeneity (for example, an object of medical interest having a functional or morphologic homogeneity, like a bone or tumor). The implementation of a neural network algorithm which does this contrast enhancement has been done on a SIMD massively parallel machine (a MasPar of 8192 processors) and the communication between its processors has been optimized.
Optimal Subcube Allocation in a Circuit-Switched Faulty Hypercube
Authors: Izadi Baback A. , Özgüner Füsun
Published: September 2003

In this paper, we present a scheme where a (d - 1)-dimensional subcube is allocated in a faulty d-dimensional circuit-switched hypercube in the presence of up to 2(d - 1) faulty nodes. The scheme is then extended to allocate a (d - 1)-dimensional subcube in the presence of a combination of faulty nodes and faulty links. Theoretical proofs and simulation results are presented to analyze the performance of the scheme.
Optimal Broadcast and Summation on Hierarchical Ring Architectures
Authors: Michail Amir
Published: September 2003

In this paper, we present several optimal and nearly optimal broadcast and summation algorithms for multiprocessors whose interconnection network consists of a hierarchy of rings. Although useful heuristics have been proposed for such systems, we present the first exact analysis of broadcast and summation on hierarchical ring architectures.
Execution-Driven Simulation of Parallel Applications
Authors: Prylli L. , Tourancheau B.
Published: September 2003

This paper presents our work on the simulation of distributed memory parallel computers. We design a distributed simulator that takes as input an application written for a MIMD computer and run it on a workstations cluster with just a recompilation of the code. The hardware of the target machine is simulated so that the behavior of the application is identical to a native run on the simulated computer with virtual timings and trace file. Moreover, our analysis sets up the conditions required to achieve a good speedup as a function of the number of simulation hosts, the network latency and the granularity of the application.
Impossibility of Synchronization in the Presence of Preemption
Authors: Ramesh S. , Shetty Chandrashekhar M.
Published: September 2003

This paper is concerned with implementation of Communicating Reactive Processes(CRP), a new paradigm unifying capabilities of synchronous and asynchronous approaches to parallel programming. Synchronous languages like Esterel, Statecharts have features like instantaneous broadcasts, logical concurrency and determinism. Asynchronous languages, like ADA and CSP, allow physical concurrency and rendezvous communication mechanisms. CRP is designed for complex real-time process control applications requiring both forms of concurrency. CRP programs can be compiled into reactive nodes that communicate using rendezvous mechanism. Implementation of rendezvous is non trivial as the following constraints are to be satisfied: 1) mutual agreement over selection of a rendezvous required between the concerned processes, 2) the implementation has to be distributed with no single process knowing instantaneously global state. This problem has been solved for Hoare's CSP, but none of these solutions can be extended to CRP. The reason is that in CRP, an enabled rendezvous can be preempted by a local reaction. In this paper, we establish that there can not exist fully distributed implementation of CRP that allows complete autonomy to reactive nodes.
Self-Stabilizing Algorithms for Tree Metrics
Authors: Datta Ajoy K. , Gonzalez Teofilo F. , Thiagarajan Visalakshi
Published: September 2003

We present algorithms for finding the diameter, centroid(s), and median(s) for tree structured networks subject to transient faults. In our solutions, the system reaches its final correct configuration in a finite time after the faults cease. The fault-tolerance is achieved using Dijkstra's paradigm of self-stabilization. A self-stabilizing algorithm, regardless of the initial system configuration, converges, in finite time, to a set of legitimate configurations.
Minimum Average Time Broadcast Graphs
Authors: Liestman Arthur L. , Pržulj Nataša
Published: September 2003

We initiate the study of minimum average time broadcast graphs - those graphs on n vertices with the fewest edges in which every vertex can broadcast in minimum average time. We find minimum average time broadcast graphs for all even n and for more than half of all odd n. In addition, we give some upper and lower bounds on the number of edges in such graphs for all n.
Messy Broadcasting
Authors: Harutyunyan Hovhannes A. , Liestman Arthur L.
Published: September 2003

In this note, we continue the study of messy broadcasting. We obtain exact values for the messy broadcasting time of complete graphs, paths, cycles, and complete d-ary trees. For hypercubes, we obtain exact values for messy broadcasting time under two of the models and present upper and lower bounds for the third model. We compare these times with (regular) broadcasting times in these graphs. We also present some simple bounds for arbitrary graphs which we use to compare the messy broadcasting times of cube-connected cycles, shuffle-exchange graphs, butterfly graphs, and DeBruijn graphs with their (regular) broadcasting times.
Global Communication on Circuit-Switched Toroidal Meshes
Authors: Peters Joseph G. , Spencer Curtis C.
Published: September 2003

In this paper, we investigate the uses of virtual channels and multiple communication ports to improve the performance of global communication algorithms for cycles and multi-dimensional toroidal meshes. We use a linear cost model to compare the performances of the best single-port algorithms for broadcasting, scattering, gossiping, and multi-scattering with algorithms that can use multiple ports simultaneously. We conclude that the use of multiple ports can enhance performance when propagation costs are dominant and virtual channels can reduce the total start-up costs. The two mechanisms interact to produce different types of trade-offs for the different communication patterns.
Broadcasting in Unlabeled Tori
Authors: Diks Krzysztof , Kranakis Evangelos , Pelc Andrzej
Published: September 2003

We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled torus: neither nodes nor links have a priori assigned labels but they know the topology and the size of the torus. Nodes can send messages of arbitrary size and we are interested in minimizing the total number of messages. A naive broadcasting algorithm in a n × n totally unlabeled torus uses 3n2 + 1 messages, while the obvious lower bound is n2 - 1. The main result of this paper is a broadcasting algorithm using 2n2 + O(n) messages. We also give a lower bound of 1.04n2 - O(n) messages. This is the first result on message complexity of broadcasting in totally unlabeled networks.
Neighbourhood Gossiping in Hypercubes
Authors: Fujita Satoshi , Perennes Stephane , Peters Joseph G.
Published: September 2003

In the neighbourhood gossiping problem, each node of a network starts with a unique message and must learn the messages of all of its neighbours. In this paper, we prove upper and lower bounds for neighbourhood gossiping in hypercubes under the single-port half-duplex and single-port full-duplex communication models.
Effective Systolic Algorithms for Gossiping in Cycles
Authors: Hromkovič Juraj , Klasing Ralf , Pardubská Dana , Waczulík Juraj , Wagener Hubert
Published: September 2003

The complexity of systolic dissemination of information in the rings of processors (cycles) in the one-way (telegraph) mode is investigated. Tight lower and upper bounds on the complexity of one-way systolic gossip are established.
A Complete Characterization of the Path Layout Construction Problem for ATM Networks with Given Hop Count and Load
Authors: Eilam Tamar , Flammini Michele , Zaks Shmuel
Published: September 2003

We investigate the time complexity of deciding the existence of layouts of virtual paths in high-speed networks, that enable a connection from one vertex to all others and have maximum hop count h and maximum edge load l, for a stretch factor of one. We prove that the problem of determining the existence of such layouts is NP-complete for every given values of h and l, except for the cases h = 2, l = 1 and h = 1, any l, for which we give polynomial-time layout constructions. Extensions for cases of a stretch factor greater than one are also discussed.
Highly Fault-Tolerant Routing in the Star and Hypercube Interconnection Networks
Authors: Rescigno A. A. , Vaccaro U.
Published: September 2003

The surviving route graph R(G, ρ)/F for a graph G, a routing ρ and a set of failures F is a graph consisting of all non-faulty vertices of G and with an edge between two vertices if there are no failures in the routing between the two vertices. Numerous papers have studied the diameter of R(G, ρ)/F as a measure of the fault-tolerance of G and ρ, assuming that the cardinality of F is strictly smaller than the connectivity of G. In this paper we study the diameter of R(G, ρ)/F, when G is either the n-star graph or the n-dimensional hypercube and ρ is any minimal length routing, under the assumption that F is any set of failures not containing all the neighbours of any vertex and |F| is at most twice the connectivity of G minus 3.
Embedding 2-Dimensional Grids Into Optimal Hypercubes with Edge-Congestion 1 or 2
Authors: Röttger Markus , Schroeder Ulf-Peter
Published: September 2003

This paper explores one-to-one embeddings of 2-dimensional grids into hypercubes. It is shown that each 2-dimensional grid can be embedded with edge-congestion 2 into its optimal hypercube (the smallest hypercube with at least as many nodes as the grid). Additionally, a technique is developed to embed many 2-dimensional grids into their optimal hypercubes with edge-congestion 1.
Embedding Grids Into Grids: Dilation Four Suffices
Authors: Ellis John , Markov Minko
Published: September 2003

We consider those instances of the problem of embedding 2-dimensional grid graphs into other 2-dimensional grids of smaller aspect ratio for which optimal solutions are as yet unknown. For those instances of the problem for which dilation two or dilation three solutions are not known, we show that none requires dilation more than four. The best upper bound previously published is six. We achieve our result by applying previously published methods, namely the so called compression and folding techniques. Optimal solutions (dilation two) are already known for all instances where the compression ratio (the ratio the width of the guest grid to the width of the host grid) is no more than two and for all instances where the compression ratio is sufficiently large. For many of the remaining instances, dilation three solutions are also known. Whether or not any instance really requires dilation greater than two remains an open question.
An Optimal Disjoint Pair of Additive Spanners for the 3D Grid
Authors: Krumme David W.
Published: September 2003

A spanner of a connected graph G is a spanning connected subgraph S. If DG(u, v) and DS(u, v) denote the distance between vertices u and v in G and S, respectively, then S is an f(x)-spanner if and only if DS(u, v) ≤ f(DG(u, v)). The value f(x) - x is the delay of the spanner. An additive spanner is one with constant delay. Given a graph G and function f(x), an interesting problem is to partition the edges of G so as to define edge-disjoint f(x)-spanners of G. This paper exhibits a pair of (x + 4)-spanners for the infinite three dimensional grid, and shows that 4 is the least integer K for which there exists an edge-disjoint pair of delay-K spanners. spanner, grid, additive spanner, parallel network.
On Hypercubes in de Bruijn Graphs
Authors: Andreae Thomas , Hintz Martin
Published: September 2003

We prove that the hypercube of odd dimension 2k + 1 is a subgraph of the de Bruijn graph of alphabet size d and diameter 2 if and only if d ≥ 3 · 2k-1. This complements previous results of Heydemann, Opatrny, and Sotteau (1994) and Andreae et al. (1995), thus yielding a complete solution of the problem of determining, for all integers m, n ≥ 2, the least number d = d(m, n) for which the hypercube of dimension m is a subgraph of the de Bruijn graph of alphabet size d and diameter n.
Tighter and Broader Complexity Results for Reconfigurable Models
Authors: Trahan Jerry L. , Bourgeois Anu G. , Vaidyanathan Ramachandran
Published: September 2003

A number of models allow processors to reconfigure their local connections to create and alter various bus configurations. This reconfiguration enables development of fast algorithms for fundamental problems, many in constant time. We investigate the ability of such models by relating time and processor bounded complexity classes defined for these models to each other and to those of more traditional models. In this work, (1) we tighten the relations for some of the models, placing them more precisely in relation to each other than was previously known (particularly, the Linear Reconfigurable Network and Directed Reconfigurable Network relative to circuit-defined classes), and (2) we include models (Fusing-Restricted Reconfigurable Mesh and Pipelined Reconfigurable Mesh) not previously considered.
A Symmetric Processor Array with Synchronous Optical Buses and Switches
Authors: Li Yueming , Tao Jianhui , Zheng S. Q.
Published: September 2003

A modified processor array with synchronous optical buses and switches for time division multiplexed optical communications is proposed. Compared with a previously proposed processor array architecture, our architecture features better flexibility, improved packet slot utilization rate and reduced average packet response time, while preserving all-optical communication paths.
A Nearly Optimal Back-Propagation Learning Algorithm on a Bus-Based Architecture
Authors: Hong Tzung-Pei , Lee Jyh-Jong
Published: September 2003

The back-propagation model is applied mainly to multiple layers of neurons with feed-forward connections. It applies the generalized delta learning rule to derive appropriate weights on connections from a set of training instances. In the past, a parallel back-propagation learning algorithm on a bus-based architecture with an infinite number of processors was proposed to speed up the learning of weights. In this paper, the parallel back-propagation learning algorithm is modified, so that it is applicable to any number of processors. The given training instances are equally partitioned and put on these processors. When learning starts, each processor searches its own training subset to update the weight matrix and to broadcast the new result. Both analytical and experimental results show that the average speed-up can reach nearly O(r) by r processors if r is much less than the number of training instances.
Fault-Tolerant Communications in Cube-Based Multiple-Bus Systems
Authors: Wu Jie
Published: September 2003

We consider routing in multiple-bus systems with faulty nodes and buses. A cube-based multiple-bus system is used as an example to demonstrate our approach. In this system, processors are partitioned into two sets based on the definition of a bipartite graph, one set is called a processor set and the other one becomes a bus set. A fault-tolerant routing scheme is proposed based on limited global information of fault distribution captured by safety level which is an integer associated with each processor and bus. A safety level is an approximated measure of the number and distribution of faulty components in the neighborhood. Each processor (also called node) is considered as an active entity while each bus is viewed as a passive one. The safety level of each bus is calculated by one of its adjacent nodes. Optimal routing between two nodes is guaranteed if the safety level of the source node is no less than the Hamming distance between the source and destination nodes. The proposed scheme is the first attempt to address fault-tolerant communication in a multiple-bus system with limited global fault information.
An Improved Embedding of Binary Trees in a Square Reconfigurable Array with Spanning Optical Buses
Authors: Qiao Chunming , Mei Yousong
Published: September 2003

This paper improves on the embedding of binary trees in a non-square Reconfigurable Array with Spanning Optical Buses (or RASOB), which was presented in [1]. Specifically, a binary tree of N2 - 1 nodes is embedded in a square N × N RASOB to achieve an optimal expansion cost, while maintaining an optimal dilation cost of 1. Such an embedding also leads to the embedding of a larger binary tree having 2k · N2 - 1 nodes, which achieves optimal load-balance and an optimal dilation cost of 1.
Embeddings of Butterflies into Hypermeshes
Authors: Kim Sook-Yeon , Kwon Oh-Heum , Chwa Kyung-Yong
Published: September 2003

Hypermeshes have been given much attention as a versatile interconnection network of parallel computers. A hypermesh is obtained from a mesh by replacing each linear connection with a hyperedge. In this paper, we show how to embed a butterfly or multiple copies of a butterfly into a hypermesh. First, a butterfly B(s) of (s + 1)2s nodes is embedded into a 2s × X hypermesh where X = 2⌊ log 2 s ⌋+ 1. Second, the butterfly B(s) is embedded into a square hypermesh. Third, multiple copies of the butterfly B(s) are embedded into a hypermesh of variable aspect ratio. The efficiency of these embeddings is measured by alignment cost, congestion, and expansion. The alignment cost of all of these embeddings is optimal. The congestion of the first and third embedding is optimal. The expansion of the first and third embedding is one if s = 2k - 1 for some integer k, otherwise, less than two. The expansion of the second embedding is 2 + ∊ (s) where ∊(s) = (2 log (s + 1) + 2)/(s + 1).
Constant Time Algorithms for Computing the Contour of Maximal Elements on a Reconfigurable Mesh
Authors: Murshed M. Manzur , Brent Richard P.
Published: September 2003

There has recently been an interest in the introduction of reconfigurable buses to existing parallel architectures. Among them the Reconfigurable Mesh (RM) draws much attention because of its simplicity. This paper presents three constant time algorithms to compute the contour of the maximal elements of N planar points on the RM. The first algorithm employs an RM of size N × N while the second one uses a 3-D RM of size [Formula: see text]. We further extend the result to k-D RM of size N1/(k - 1) × N1/(k - 1) × … × N1/(k - 1).
A Selection Algorithm for X + Y on Mesh
Authors: Anand Tarun , Gupta Phalguni
Published: September 2003

This paper presents a selection algorithm for finding the k-th largest element in the cartesian sum of two sets X and Y, each of size n, on a mesh connected model. The algorithm has a time complexity of [Formula: see text], using P processors, where P < n2. The algorithm is adaptive but [Formula: see text] away from cost optimality.
Hamilton Cycle Decomposition of the Butterfly Network
Authors: Bermond J.-C. , Darrot E. , Delmas O. , Perennes S.
Published: September 2003

In this paper, we prove that the wrapped Butterfly graph WBF(d,n) of degree d and dimension n is decomposable into Hamilton cycles. This answers a conjecture of Barth and Raspaud who solved the case d = 2.
On a Sublinear Time Parallel Construction of Optimal Binary Search Trees
Authors: Karpinski Marek , Rytter Wojciech
Published: September 2003

We show how to construct optimal binary search trees in O(n1 - ∊ log (n)) time with the total work O(n2 + 2 ∊), for arbitrarily small constant [Formula: see text]. This is optimal within factor n2 ∊ with respect to the best known sequential algorithm given by Knuth, which needs only O(n2) time due to a monotonicity property of optimal binary search trees, see [6].
A Parallel Algorithm for Finding a Perfect Matching in a Planar Graph
Authors: Bampis E. , Giannakos A. , Karzanov A. , Manoussakis Y. , Milis I.
Published: September 2003

We present au intuitive and simple O( log 2 n log Φ) time, O(n2 M(n)) processor parallel algorithm for finding a perfect matching in a planar graph, where n is the order, Φ is the number of the distinct perfect matchings of the graph and M(n) is the best sequential complexity of matrix multiplication of size n. The algorithm runs on a CRCW PRAM. Clearly, our algorithm belongs to the class NC if the number of perfect matchings is polynomially bounded in the size of the input graph.
Mapping Fortran Programs to Single Assignment Semantics for Efficient Parallelization
Authors: Evripidou Paraskevas , Barry Robert
Published: September 2003

This paper presents Mustang, a system that automatically parallellizes Fortran programs by mapping them to single assignment semantics. Specifically, sequential Fortran source programs are translated into IF1, a machine-independent dataflow graph description language that is the intermediate form for the SISAL language. During this translation, Parfrase 2 is used to parse the source program perform dependency analysis and to detect opportunities for parallelization which are then explicitly introduced into the IF1 program. The resulting IF1 program is then processed by the Optimizing SISAL Compiler which produces parallel executables on multiple target platforms. A working prototype has been developed and tested. The execution results of several Livermore Loops are presented and compared against Fortran and SISAL implementations on two different platforms. The initial results obtained provide proof of concept that Fortran can be mapped to Single Assignment Semantics without sacrificing efficiency.
Specification and Verification of the ATMR Protocol Using UNITY: Part 1: Modeling and Specification of the Protocal
Authors: Charpentier Michel , Padiou Gérard
Published: September 2003

We propose a description and validation of the ATMR protocol within the UNITY formalism. This formal description helps us understand precisely the mechanisms this protocol involves. In particular, we have noted the use of an incorrect detection algorithm to generate reset slots. In this first part, we provide an operational description using the UNITY programming notation as well as a specification of the main correctness properties in the UNITY temporal logic. A second part [2] is dedicated to a hand-made correctness proof. The proof shows that the model satisfies the specification despite this spurious detection. In this study, we apply a general development process based upon the UNITY formalism. During this process, we tune the program specification in order to make the later validation step easier, in the same way as the inclusion of traces, breakpoints, and assertions prepares a program for its quality assurance tests.
Specification and Verification of the ATMR Protocol Using UNITY: Part 2: Correctness Proof
Authors: Charpentier Michel , Padiou Gérard
Published: September 2003

We propose a description and validation of the ATMR protocol within the UNITY formalism. This formal description helps us understand precisely the mechanisms this protocol involves. In particular, we have noted the use of an incorrect detection algorithm to generate reset slots. An operational description using the UNITY programming notation and a specification of the main correctness properties in the UNITY temporal logic are given in a previous part [2]. This second part is dedicated to a hand-made correctness proof. The proof shows that the model satisfies the specification despite the spurious detection in the reset generation mechanism.