The Experts below are selected from a list of 10356 Experts worldwide ranked by ideXlab platform
Basel A. Mahafzah - One of the best experts on this subject based on the ideXlab platform.
-
parallel quicksort algorithm on Otis hyper hexa cell optoelectronic architecture
Journal of Parallel and Distributed Computing, 2020Co-Authors: Aryaf Aladwan, Basel A. Mahafzah, Rawan Zaghloul, Ahmad ShariehAbstract:Abstract In the last two decades, widespread attention has been paid in parallelizing algorithms, such as sorting and searching, for computationally intensive applications. Several interconnection networks were demonstrated for that purpose; such as hypercube and Hyper Hexa-Cell (HHC). However, the leverage of optical links in Optical Transpose Interconnection Systems (Otis) stimulates the researchers toward developing optoelectronic architectures that utilize the optical links in addition to the electronic links; such as, Otis-hypercube and Otis-HHC. In this paper, we introduced a parallel quicksort algorithm for the Otis-HHC optoelectronic architecture. This algorithm has been evaluated analytically and by simulation in terms of run time, speedup, and efficiency, where a set of simulation runs were carried out on different input data distributions types with various sizes. Thus, simulation results supported the analytical evaluation and met the expectations in which they showed good performance in terms of speedup and efficiency.
-
Parallel heuristic local search algorithm on Otis hyper hexa-cell and Otis mesh of trees optoelectronic architectures
Applied Intelligence, 2019Co-Authors: Aryaf Al-adwan, Ahmad Sharieh, Basel A. MahafzahAbstract:Heuristic local search algorithms have achieved good results in tackling combinatorial optimization problems, such as Travelling Salesman Problem (TSP). One of the well-known local search algorithms is the 2-opt algorithm. As a local search algorithm, 2-opt has achieved approximate optimal solutions for TSP within a reasonable time, especially for small data instances. However, solving large data instances of TSP using 2-opt requires extensive computation and considerable CPU time. Therefore, this paper presents a parallel version of the 2-opt algorithm, exploiting the features of Optical Transpose Interconnection System (Otis) in solving the TSP. In this paper, we present the Parallel Repetitive 2-Opt (PRTO) algorithm for solving symmetric TSP on Otis Hyper Hexa-Cell (Otis-HHC) and Otis Mesh of Trees (Otis-MOT) optoelectronic architectures. We assess the performance of our algorithm analytically in terms of parallel time complexity, speedup, efficiency, cost, and communication cost on both optoelectronic architectures. Furthermore, a set of simulation experiments is conducted on various instances from the standard TSP library. The simulation results confirm that our algorithm is efficient regarding speedup and efficiency. For instance, the PRTO algorithm achieves a speedup of 32.9 for 6880 cities over Otis-HHC with 36 processors. Moreover, the superiority of PRTO algorithm is shown through solving the TSP on Otis-HHC and Otis-MOT; its performance has been compared with the performance of the Parallel Repetitive Nearest Neighbor (PRNN) algorithm in terms of speedup, efficiency, and solution quality. For example, as a best case, the PRTO algorithm has shown 34 times improved speedup over the PRNN algorithm.
-
Solving traveling salesman problem using parallel repetitive nearest neighbor algorithm on Otis-Hypercube and Otis-Mesh optoelectronic architectures
The Journal of Supercomputing, 2018Co-Authors: Aryaf Al-adwan, Basel A. Mahafzah, Ahmad ShariehAbstract:Over the past years, researchers drew their attention to propose optoelectronic architectures, including optical transpose interconnection system (Otis) networks. On the other hand, there are limited attempts devoted to design parallel algorithms for applications that could be mapped on such optoelectronic architectures. Thus, exploiting the attractive features of Otis networks and investigating their performance in solving combinatorial optimization problems become a great necessity. In this paper, a parallel repetitive nearest neighbor algorithm for solving the symmetric traveling salesman problem on Otis-Hypercube and Otis-Mesh optoelectronic architectures is presented. This algorithm has been evaluated analytically and by simulation on both optoelectronic architectures in terms of number of communication steps, parallel run time, speedup, efficiency, cost and communication cost. The simulation results attained almost near-linear speedup and high efficiency among the two selected optoelectronic architectures, where Otis-Hypercube gained better results in comparison with Otis-Mesh.
-
The Otis hyper hexa-cell optoelectronic architecture
Computing, 2012Co-Authors: Basel A. Mahafzah, Azzam Sleit, Nesreen A. Hamad, Elham F. Ahmad, Tasneem M. Abu-kabeerAbstract:Optical transpose interconnection system (Otis) is an optoelectronic architecture that promises to be a great choice for future-generation parallel systems. Otis combines the advantages of electronic and optical links, where electronic links are used for short distances which require low material cost, and optical links are used for long distances which provide high speed network with low power consumption. Taking into account the advantageous characteristics of Otis and based on the attractive properties of hyper hexa-cell (HHC) interconnection topology from low diameter and good minimum node degree, this paper introduces a new optoelectronic architecture referred to as Otis hyper hexa-cell (OHHC). This paper also provides an evaluation and a comparison of the new topology with Otis-mesh in terms of the following topological properties: size, diameter, maximum and minimum node degree, bisection width, total cost and optical cost. The results of this study proved the excellence of the proposed OHHC over Otis-mesh in terms of diameter, minimum node degree, bisection width, and optical cost.
-
Performance evaluation of broadcast and global combine operations in all-port wormhole-routed Otis-Mesh interconnection networks
Cluster Computing, 2010Co-Authors: Basel A. Mahafzah, Ruby Y. Tahboub, Omar Y. TahboubAbstract:Otis (Optical Transpose Interconnection System) optoelectronic architecture is an attractive high-speed interconnection network. As a continuation for the research work performed on Otis, this paper investigates broadcast and global combine communication operations on the promising all-port wormhole-routed Otis-Mesh using the Extended Dominating Node (EDN) approach, referred to as EDN-Otis-Mesh. The performance of broadcast and global combine operations is evaluated, both analytically and by simulation, in terms of the number of communication steps, latency, and latency improvement. A comparative study is conducted among three interconnection networks’ architectures: the single-port wormhole-routed Otis-Mesh, all-port wormhole-routed Otis-Mesh, and all-port wormhole-routed EDN-Otis-Mesh. The obtained analytical and simulation results show that the broadcast and global combine operations on all-port EDN-Otis-Mesh significantly outperform the single-port and all-port Otis-Mesh.
Behrooz Parhami - One of the best experts on this subject based on the ideXlab platform.
-
load balancing on swapped or Otis networks
Journal of Parallel and Distributed Computing, 2009Co-Authors: Chenggui Zhao, Wenjun Xiao, Behrooz ParhamiAbstract:Abstract Existing local iterative algorithms for load-balancing are ill-suited to many large-scale interconnection networks. The main reasons are complicated Laplace spectrum computations and flow scheduling strategies. Many large-scale networks are modular and/or hierarchically structured, a prime example being the class of swapped or Otis networks that have received much attention in recent years. We propose a new local scheme, called DED-X, for load-balancing on homogeneous and heterogeneous swapped/Otis networks. Our scheme needs spectral information only for the much smaller basis or factor graph, which is of size O ( n ) rather than O ( n 2 ) , and it schedules load flow on intragroup and intergroup links separately. We justify the improvements offered by DED-X schemes over traditional X schemes analytically and verify the advantages of our approach, in terms of efficiency and stability, via simulation.
-
Swapped (Otis) Networks Built of Connected Basis Networks Are Maximally Fault Tolerant
IEEE Transactions on Parallel and Distributed Systems, 2009Co-Authors: Weidong Chen, Wenjun Xiao, Behrooz ParhamiAbstract:An optical transpose interconnection system (Otis) network with n2 nodes is a two-level swapped architecture built of n copies of an n-node basis network that constitute its clusters. A simple rule for intercluster connectivity (node j in cluster i connected to node i in cluster j) leads to regularity, modularity, packageability, fault tolerance, and algorithmic efficiency of the resulting networks. We prove that an Otis (swapped) network with a connected basis network possesses maximal fault tolerance, regardless of whether its basis network is maximally fault tolerant. We also show how the corresponding maximal number of node-disjoint paths between two nodes of a swapped network can be algorithmically constructed in a manner that is independent of the existence and construction of node-disjoint paths within its basis network. Our results are stronger than previously published results and they replace a number of proofs and constructions in the literature for specific basis networks. Additionally, we use our parallel path constructions to establish that the fault diameter and wide diameter of an Otis network is no more than 4 units greater than its diameter.
-
the hamiltonicity of swapped Otis networks built of hamiltonian component networks
Information Processing Letters, 2005Co-Authors: Behrooz ParhamiAbstract:A two-level swapped (also known as optical transpose interconnect system, or Otis) network with n2 nodes is built of n copies of an n-node basis network constituting its clusters. A simple rule for intercluster connectivity (node j in cluster i connected to node i in cluster j for all i ≠ j) leads to regularity, modularity, packageability, fault tolerance, and algorithmic efficiency of the resulting networks. We prove that a swapped network is Hamiltonian if its basis network is Hamiltonian. This general closure property for Hamiltonicity under swap or Otis composition replaces a number of proofs in the literature for specific basis networks and obviates the need for proving Hamiltonicity for many other basis networks of potential practical interest.
Sartaj Sahni - One of the best experts on this subject based on the ideXlab platform.
-
Matrix multiplication on the Otis-Mesh optoelectronic computer
IEEE Transactions on Computers, 2001Co-Authors: Chih-fang Wang, Sartaj SahniAbstract:We develop algorithms to multiply two vectors, a vector and a matrix, and two matrices on an Otis-Mesh optoelectronic computer. Two mappings, group row and group submesh, of a matrix onto an Otis-Mesh are considered and the relative merits of each compared. We show that our algorithms to multiply a column and row vector use an optimal number of data moves for both the group row and group submesh mappings, our algorithm to multiply a row vector and a column vector is optimal for the group row mapping, and our algorithm to multiply a matrix by a column vector is optimal for the group row mapping.
-
image processing on the Otis mesh optoelectronic computer
IEEE Transactions on Parallel and Distributed Systems, 2000Co-Authors: Chih-fang Wang, Sartaj SahniAbstract:We develop algorithms for histogramming, histogram modification, Hough transform, and image shrinking and expanding on an Otis-mesh optoelectronic computer. Our algorithm for the Hough transform is based upon a mesh algorithm for the Hough transform which is also developed in this paper. This new mesh algorithm improves upon the previous mesh Hough transform algorithms.
-
matrix multiplication on the Otis mesh optoelectronic computer
Proceedings. 6th International Conference on Parallel Interconnects (PI'99) (Formerly Known as MPPOI), 1999Co-Authors: Chih-fang Wang, Sartaj SahniAbstract:We develop algorithms to multiply two vectors, a vector and a matrix, and two matrices on an Otis-Mesh optoelectronic computer. Two mappings, group row and group sub-mesh of a matrix onto an Otis-Mesh are considered and the relative merits of each compared.
-
randomized routing selection and sorting on the Otis mesh
IEEE Transactions on Parallel and Distributed Systems, 1998Co-Authors: Sanguthevar Rajasekaran, Sartaj SahniAbstract:The Optical Transpose Interconnection System (Otis) is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. In this paper we present efficient algorithms for packet routing, sorting, and selection on the Otis-Mesh. The diameter of an N/sup 2/-processor Otis-Mesh is 4/spl radic/N-3. We present an algorithm for routing any partial permutation in 4/spl radic/N+o(/spl radic/N) time. Our selection algorithm runs in time 6/spl radic/N+o(/spl radic/N) and our sorting algorithm runs in 8/spl radic/N+o(/spl radic/N) time. All these algorithms are randomized and the stated time bounds hold with high probability. Also, the queue size needed for these algorithms is O(1) with high probability.
-
basic operations on the Otis mesh optoelectronic computer
International Conference on Parallel Processing, 1998Co-Authors: Chih-fang Wang, Sartaj SahniAbstract:In this paper we develop algorithms for some basic operations-broadcast, window broadcast, prefix sum, data sum, rank, shift, data accumulation, consecutive sum, adjacent sum, concentrate, distribute, generalize, sorting, random access read and write-on the Otis-Mesh model. These operations are useful in the development of efficient algorithms for numerous application.
Ahmad Sharieh - One of the best experts on this subject based on the ideXlab platform.
-
parallel quicksort algorithm on Otis hyper hexa cell optoelectronic architecture
Journal of Parallel and Distributed Computing, 2020Co-Authors: Aryaf Aladwan, Basel A. Mahafzah, Rawan Zaghloul, Ahmad ShariehAbstract:Abstract In the last two decades, widespread attention has been paid in parallelizing algorithms, such as sorting and searching, for computationally intensive applications. Several interconnection networks were demonstrated for that purpose; such as hypercube and Hyper Hexa-Cell (HHC). However, the leverage of optical links in Optical Transpose Interconnection Systems (Otis) stimulates the researchers toward developing optoelectronic architectures that utilize the optical links in addition to the electronic links; such as, Otis-hypercube and Otis-HHC. In this paper, we introduced a parallel quicksort algorithm for the Otis-HHC optoelectronic architecture. This algorithm has been evaluated analytically and by simulation in terms of run time, speedup, and efficiency, where a set of simulation runs were carried out on different input data distributions types with various sizes. Thus, simulation results supported the analytical evaluation and met the expectations in which they showed good performance in terms of speedup and efficiency.
-
Parallel heuristic local search algorithm on Otis hyper hexa-cell and Otis mesh of trees optoelectronic architectures
Applied Intelligence, 2019Co-Authors: Aryaf Al-adwan, Ahmad Sharieh, Basel A. MahafzahAbstract:Heuristic local search algorithms have achieved good results in tackling combinatorial optimization problems, such as Travelling Salesman Problem (TSP). One of the well-known local search algorithms is the 2-opt algorithm. As a local search algorithm, 2-opt has achieved approximate optimal solutions for TSP within a reasonable time, especially for small data instances. However, solving large data instances of TSP using 2-opt requires extensive computation and considerable CPU time. Therefore, this paper presents a parallel version of the 2-opt algorithm, exploiting the features of Optical Transpose Interconnection System (Otis) in solving the TSP. In this paper, we present the Parallel Repetitive 2-Opt (PRTO) algorithm for solving symmetric TSP on Otis Hyper Hexa-Cell (Otis-HHC) and Otis Mesh of Trees (Otis-MOT) optoelectronic architectures. We assess the performance of our algorithm analytically in terms of parallel time complexity, speedup, efficiency, cost, and communication cost on both optoelectronic architectures. Furthermore, a set of simulation experiments is conducted on various instances from the standard TSP library. The simulation results confirm that our algorithm is efficient regarding speedup and efficiency. For instance, the PRTO algorithm achieves a speedup of 32.9 for 6880 cities over Otis-HHC with 36 processors. Moreover, the superiority of PRTO algorithm is shown through solving the TSP on Otis-HHC and Otis-MOT; its performance has been compared with the performance of the Parallel Repetitive Nearest Neighbor (PRNN) algorithm in terms of speedup, efficiency, and solution quality. For example, as a best case, the PRTO algorithm has shown 34 times improved speedup over the PRNN algorithm.
-
Solving traveling salesman problem using parallel repetitive nearest neighbor algorithm on Otis-Hypercube and Otis-Mesh optoelectronic architectures
The Journal of Supercomputing, 2018Co-Authors: Aryaf Al-adwan, Basel A. Mahafzah, Ahmad ShariehAbstract:Over the past years, researchers drew their attention to propose optoelectronic architectures, including optical transpose interconnection system (Otis) networks. On the other hand, there are limited attempts devoted to design parallel algorithms for applications that could be mapped on such optoelectronic architectures. Thus, exploiting the attractive features of Otis networks and investigating their performance in solving combinatorial optimization problems become a great necessity. In this paper, a parallel repetitive nearest neighbor algorithm for solving the symmetric traveling salesman problem on Otis-Hypercube and Otis-Mesh optoelectronic architectures is presented. This algorithm has been evaluated analytically and by simulation on both optoelectronic architectures in terms of number of communication steps, parallel run time, speedup, efficiency, cost and communication cost. The simulation results attained almost near-linear speedup and high efficiency among the two selected optoelectronic architectures, where Otis-Hypercube gained better results in comparison with Otis-Mesh.
Michael C Smith - One of the best experts on this subject based on the ideXlab platform.
-
barley tolerance of russian wheat aphid hemiptera aphididae biotype 2 herbivory involves expression of defense response and developmental genes
Plant Signaling & Behavior, 2012Co-Authors: Murugan Marimuthu, Michael C SmithAbstract:The Russian wheat aphid, Diuraphis noxia (Kurdjumov), is an invasive insect pest that causes serious yield losses in bread wheat, Triticum aestivum L., durum wheat, T. turgidum L and barley, Hordeum vulgare L. Successful management of D. noxia has been achieved through resistant varieties via plant antixenosis (aphid non-preference), antibiosis (reduced aphid growth or fecundity), tolerance (plant compensatory growth after aphid feeding), or a combination of each. Previous phenotyping experiments revealed that plants of the variety Stoneham resist D. noxia damage via tolerance. In the present study, genes involved in upstream regulation of jasmonic acid (JA), salicylic acid (SA), ethylene (ET), auxin (AUX) and abscisic acid (ABA) biosynthetic pathways were monitored using qRT-PCR in Stoneham and susceptible Otis barley plants after D. noxia biotype 2 feeding. Results indicate that D. noxia tolerance in Stoneham plants is related to greater constitutive expression of JA-, ET- and AUX-biosynthetic pathway genes than in susceptible Otis plants, suggesting the possibility of immediate plant adjustments due to the stress of D. noxia feeding. There was limited induction of genes in the ET-(ACCS) and IAA (TDC) pathways in Stoneham tissues after D. noxia feeding. JA pathway genes upregulated in Otis tissues after D. noxia infestation failed to successfully defend Otis plants. AUX and ABA transcripts in Otis may be associated with developmental collapses resulting from source and sink adjustment failures.
