Dissertations / Theses on the topic 'Hypercubes'

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes.

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes
This Ph. D. Manuscript is built around the notion of graph embedding. An embedding of a graph G is an application mapping the vertices of G to elements of another structure, and preserving some properties of G. There are two types of embeddings. The combinatorial embeddings map the vertices of a graph G to the vertices of a graph H. The usual property that is preserved is the adjacency between vertices. In this thesis, we consider the isometric embeddings, preserving in addition the distances between vertices. We give some structural characterizations for families of graphs isometrically embeddable in hypercubes or Hamming graphs. The topological embeddings aim at drawing a graph G on some surface. Vertices are mapped to distinct points of the surface and the edges are represented by continuous curves linking these points. Is it possible to draw a graph G so that the edges do not cross eachother ? If not, what is the minimum number of crossings of a drawing of G ? We deal with these questions on different surfaces, or in relation with some graph operations as direct product or zip product

La quantification des incertitudes est essentielle à la bonne maîtrise de la production des réservoirs pétroliers. Ce problème est complexe car l’impact des paramètres incertains sur la production est souvent non-régulier. Du fait du coût important d’une simulation numérique d’écoulement, les méthodes traditionnelles d’analyse de risque sont basées sur un modèle approché du modèle d’écoulement. Ce modèle, construit à partir de plans d’expériences supposant un comportement polynomial de la réponse, ignore les non-régularités. L’objectif de cette thèse est la mise en place d’un formalisme de modélisation de réponses non-régulières. Nous proposons de construire des plans évolutifs afin d’intégrer graduellement les non-régularités. Cette approche est inspirée conjointement de méthodes géostatistiques et de plans d’expériences. En partant d’une surface de réponse initiale, la méthodologie consiste à déterminer itérativement de nouvelles simulations afin d’enrichir le dispositif expérimental et ainsi améliorer l’approximation de la réponse. Différents critères d’ajout de simulations sont proposés. Nous préconisons l’intégration de l’information apportée par les extrema et les points de dérivée partielle nulle de l’approximation. De plus, l’ajout d’information fictive par points pilotes permet une optimisation de la prédictivité de l’approximation ainsi que la détermination de nouveaux points candidats à la simulation. Cette méthodologie originale d’ajustement de surfaces complexes a montré son efficacité, en terme de modélisation comme en terme de réduction du nombre de simulations, notamment pour une quantification d’incertitudes pour deux cas de réservoir pétrolier
Quantification of uncertainty in reservoir performance is an essential phase of oil field evaluation and production. Due to the large number of parameters and the physical complexity of the reservoir, fluid flow models can be computationally time consuming. Traditional uncertainty management is thus routinely performed using proxy models of the fluid flow simulator, following experimental design methodology. However, this approach often ignores the irregularity of the response. The objective of the thesis is to construct non-linear proxy models of the fluid flow simulator. Contrary to classical experimental designs which assume a polynomial behavior of the response, we build evolutive experimental designs to fit gradually the potentially non-linear shape of uncertainty. This methodology combines the advantages of experimental design with geostatistical methods. Starting from an initial trend of the uncertainty, the method determines iteratively new simulations that might bring crucial information to update the estimation of the uncertainty. Four criteria of adding new simulations are proposed. We suggest performing simulation at the extremes and the null derivative points of the approximation in order to better characterize irregularity. In addition, we propose an original way to increase the prior predictivity of the approximation using pilot points. The pilot points are also good candidates for simulation. This methodology allows for an efficient modeling of highly non-linear responses, while reducing the number of simulations compared to latin hypercubes. This work can potentially improve the efficiency in decision making under uncertainty

Les mesures de complexité des fonctions booléennes capturent divers aspects de la difficulté du calcul d'une fonction et leur étude consiste à trouver des connexions entre différentes mesures de complexité. Dans la première partie de cette thèse, nous introduisons et étudions la complexité de jeux de certificats, une mesure de complexité basée sur la probabilité de gagner un jeu dans lequel deux joueurs reçoivent des entrées avec des valeurs de fonctions différentes et doivent produire un indice i pour lequel leurs entrées diffèrent, sans communiquer. Nous donnons des bornes supérieures et inférieures pour les stratégies à base de pièces privées, de pièces publiques, d'intrication partagée et de non-signalisation, et nous prouvons quelques résultats de séparations. D'une part, nous montrons que la complexité dans le cas des pièces publiques est majorée par les complexités de requête aléatoire et de certificat. D'autre part, nous montrons qu'elle est minorée par la complexité fractionnelle de certificat, ce qui en fait un bon candidat pour trouver des bornes inférieures fortes sur la complexité de requête aléatoire. La complexité dans le cas des pièces privées est minorée par la complexité de requête aléatoire à erreur nulle. Nous utilisons la non-signalisation, une notion d'information quantique, pour minorer par n la complexité de jeux de certificats quantiques de la fonction OR, dont la complexité de requête quantique est de Θ(√n), puis nous montrons que ce "goulot d'étranglement de non-signalisation" s'applique à toutes les fonctions à sensibilité, à sensibilité de bloc ou à sensibilité de bloc fractionnaire élevée. Nous considérons également la version mono-bit des jeux de certificats, où les entrées des deux joueurs sont restreints à une distance de Hamming de 1. Nous prouvons que la version mono-bit de la complexité de jeux de certificats avec aléa partagé est égale à la sensibilité à un facteur constant près, ce qui donne une nouvelle caractérisation de la sensibilité. D'autre part, la version mono-bit de la complexité de jeux de certificats avec aléa privé est égale à λ2, où λ est la sensibilité spectrale. Dans la deuxième partie de cette thèse, nous revisitons la célèbre preuve de la conjecture de la sensibilité par Hao Huang. En utilisant des techniques spectrales, Huang a prouvé que tout sous-graphe de l'hypercube Hn de dimension n induit sur plus de la moitié des sommets a un degré maximal d'au moins √n. Combiné avec des travaux antérieurs, ce résultat a complété une preuve de la conjecture de la sensibilité. Nous en donnons une preuve alternative en utilisant seulement la dépendance linéaire des vecteurs associés aux sommets de l'hypercube. Notre approche permet de mieux comprendre les propriétés structurelles du sous-graphe induit, en plus du plus grand degré. En particulier, nous prouvons que dans tout sous-graphe induit de Hn avec plus de la moitié du nombre de sommets, il existe deux sommets, l'un de parité impaire et l'autre de parité paire, chacun ayant au moins n sommets à une distance au plus égale à 2. Comme application, nous montrons que pour toute fonction booléenne f, le degré polynomial est majoré par le produit de la sensibilité 0 et de la sensibilité 1, s0(f)s1(f), une affirmation strictement plus forte qui implique le théorème de Huang. Nous obtenons également des relations structurelles pour les sous-graphes induits à distance 3. Un ingrédient clé de la preuve de Huang était des hypercubes signés avec la propriété que chaque cycle de longueur 4 est affecté d'un signe négatif. Nous examinons en détail cette signature et donnons une signature quasi-optimale qui utilise le nombre minimum de bords négatifs tout en garantissant que chaque cycle de longueur 4 est négatif. Ce problème s'avère être lié à l'un des problèmes d'Erdös sur le plus grand sous-graphe de l'hypercube exempt de 4-cycles
Complexity measures of Boolean functions capture various aspects of the hardness of computing a function and their study is about finding connections between different complexity measures. In the first part of this thesis, we introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game in which two players are given inputs with different function values and are asked to output some index i where their inputs differ, in a zero-communication setting. We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations. We show that complexity in the public coin model is bounded above by Randomised query and Certificate complexities. On the other hand, it is bounded below by fractional certificate complexity, making it a good candidate to prove strong lower bounds on randomised query complexity. Complexity in the private coin model is bounded below by zero-error randomised query complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. While public coin certificate game complexity is bounded above by randomised query complexity, quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of n on the quantum certificate game complexity of the OR function, whose quantum query complexity is Θ(√n) and then go on to show that this "non-signaling bottleneck" applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity. We also consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1. We prove that the single-bit version of certificate game complexity with shared randomness is equal to sensitivity up to constant factors, thus giving a new characterization of sensitivity. On the other hand, the single-bit version of certificate game complexity with private randomness is equal to λ2, where λ is the spectral sensitivity. In the second part of this thesis, we revisit the celebrated proof of the sensitivity conjecture by Hao Huang. Using spectral techniques, Huang proved that every subgraph of the hypercube Hn of dimension n induced on more than half the vertices has maximum degree at least √n. Combined with earlier work, this completed a proof of the sensitivity conjecture. We show an alternate proof of Huang's result using only linear dependency of vectors associated with the vertices of the hypercube. Our approach helps gain insight on more structural properties of the induced subgraph in addition to the largest degree. In particular, we prove that in any induced subgraph of Hn with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application, we show that for any Boolean function f, the polynomial degree is bounded above by the product of 0-sensitivity and 1-sensitivity, s0(f)s1(f), a strictly stronger statement which implies Huang's theorem. We also obtain structural relations for induced subgraphs at distance 3. A key implement in Huang's proof was signed hypercubes with the property that every cycle of length 4 is assigned a negative sign. We take a detailed look at this signature and give a nearly optimal signature that uses the minimum number of negative edges while ensuring that every 4-cycle is negative. This problem turns out to be related to one of Erdös' problems on the largest 4-cycle free subgraph of the hypercube

Nos últimos anos, máquinas maciçamente paralelas, compostas de centenas de processadores, vem sendo estudadas como uma alternativa para a construção de supercomputadores. Neste novo conceito de processamento de dados, grandes velocidades são alcançadas através da cooperação entre os diversos elementos processadores na resolução de um problema. Grande parte das máquinas maciçamente paralelas encontradas no mercado utilizam-se da topologia hipercúbica para a interconexão de seus múltiplos processadores, ou podem ser configuradas como tal. Uma alternativa interessante para o compartilhamento da capacidade de processamento destas máquinas é sua utilização como computador agregado a uma rede, servindo a diversos usuários [DUT 91]. Desta forma, a máquina hipercúbica se comporta como um banco de processadores, que permite que cada usuário aloque parte de seus processadores para seu uso pessoal. Isto resulta em um aumento no desempenho da rede ao nível de supercomputadores com um custo relativamente baixo e viabiliza a construção de máquinas hipercúbicas com altas dimensões, evitando que estas sejam sub-utilizadas. Neste tipo de contexto, cabe ao sistema operacional atender as requisições dos usuários do hipercubo compartilhado de forma eficiente, a fim de evitar uma rápida fragmentação do cubo e de não exceder o tempo máximo de espera de uma determinada aplicação. A partir dos algoritmos propostos é apresentada a definição de um servidor de processadores para o compartilhamento de uma máquina multiprocessadora hipercúbica em uma rede de estações de trabalho. Algumas funções deste servidor são implementadas por um protótipo denominado Sub-Cube RPC. Com o objetivo de analisar o comportamento da rede de estações em relação a inclusão de um novo recurso a ser compartilhado, foi desenvolvido, juntamente com o grupo de Avaliação de Desempenho ADMP, um simulador para o ambiente SUN/UNIX. Através desta ferramenta e dos tempos de resposta obtidos pelo protótipo do servidor desenvolvido é possível avaliar o custo que o tráfego gerado pelo servidor adiciona à rede, sendo possível a manipulação de parâmetros da rede e do servidor. Os resultados obtidos nas versões paralelas implementadas são comparados com o desempenho das versões seqüenciais. Para viabilizar esta comparação, todos os algoritmos seqüenciais encontrados na literatura também foram implementados na linguagem "C" no ambiente alvo UNIX e encontram-se em anexo. As versões paralelas foram implementadas utilizando-se recursos da própria rede de estações, através de diretivas socket, e também em Transputers na linguagem C paralela. O protótipo do servidor de processadores foi implementado como um servidor RPC para uma rede de estações UNIX também na linguagem "C". A ferramenta de simulação para o funcionamento do servidor foi implementada na linguagem "C" e seu sistema de entrada de dados e visualização utiliza a interface X-Windows. Com os resultados deste trabalho se pode ter uma boa idéia dos efeitos e das dificuldades encontradas na paralelização dos algoritmos de alocação e gerência de processadores para máquinas Hipercúbicas. As informações contidas no trabalho auxiliam na melhoria do tempo de resposta dos algoritmos seqüenciais atuais e no desenvolvimento de novos algoritmos com mais recursos e ainda assim viáveis em ambientes interativos, graças a utilização de paralelismo. O protótipo Sub-Cube RPC demonstra como os algoritmos estudados neste trabalho podem ser aplicados na construção de um servidor de processadores para máquinas multiprocessadas. O protótipo servirá como base para a implementação de um servidor semelhante no CPGCC/UFRGS, que colocará uma placa de Transputers à disposição da rede de estações do grupo de processamento paralelo.
In the last years massively parallel machines, build with hundreds of processors, are becoming an alternative for the construction of supercomputers. In this new concept of data processing, high performance is achieved by processor cooperation in the resolution of a problem. A great part of the commercial massively parallel machines utilizes the hypercubic topology to interconnect their multiple processors, or may be configured as hypercubes. A very interesting alternative for sharing the processing power of this machines is their utilization as aggregated computer in a network, serving various users [DUT 91]. In such environment, the hypercube behaves like a processor server, permitting the users to allocate part of its processors for local use. This result in a enhancement in the performance of workstation networks to the level of supercomputers and allow higher dimension hypercubes to be better utilized. In such environment the operating system is responsible for serving the users of a shared multiprocessor in a efficient way, not allowing a quick fragmentation of the hypercube and observing the maximal waiting time for the applications. The algorithms for processor allocation and management are responsible for obtention and control of one or more processors of the shared machine for the user's task execution. In this study, parallel versions of the most important algorithms for processor allocation and management in hypercubes found in the literature are proposed. The intention with this paralelization is to achieved a better response time of the more complex algorithms, making their use possible in a real time sharing environment. Because the allocation is considered the most important part of the processor server, the utilization of more complex algorithms allows a better utilization of the shared processors, resulting in a performance increase of the parallel machine. Based on the proposed algorithms, a processor server is defined for sharing a hypercubic multiprocessor in a workstation network. Some functions of this server are implemented in a prototype called Sub-Cube RPC. To analyze the behavior of the network, in relation to the inclusion of this new shared resource, a simulator for the SUN/UNIX environment has been developed together with the Performance Evaluation Group ADMP. With this tool and with the response times of the developed server prototype, it is possible to evaluate the cost of the additional network traffic generated by the server, with the possibility to change parameters of the server and network. The results obtained in the implemented parallel versions are compared with the performance of the sequential algorithms. To make this comparison possible all the sequential algorithms found in the literature are also implemented in the "C" language and can be found in annex. The parallel versions were implemented using network resources, through the socket directive, and also using Transputers in parallel "C". The processor server prototype was implemented as a RPC server for an UNIX network, also in the "C" language. The simulation tool was coded in "C" and the I/O interface use the X-Windows protocol. The results of this study may give a background about the effects and difficulties found in the pa ralelization of the allocation algorithms for the hypercubic machines. The information found in this study will help the operating system designer to obtain a better response time of the sequential algorithms found in the literature and in the development of new and more complex algorithms that will be still practicable in a real time environment due to parallelism utilization. The Sub-Cube RPC prototype demonstrates how the algorithms studied in this work can be applied in the construction of a processor server for multiprocessors. The prototype is the first step for the implementation of a similar server in the CPGCC/UFRGS that will share a Transputer board in a network of workstations from the parallel processing group.

This item is only available in print in the UCF Libraries. If this is your Honors Thesis, you can help us make it available online for use by researchers around the world by following the instructions on the distribution consent form at http://library.ucf.edu/Systems/DigitalInitiatives/DigitalCollections/InternetDistributionConsentAgreementForm.pdf You may also contact the project coordinator, Kerri Bottorff, at kerri.bottorff@ucf.edu for more information.
Bachelors
Engineering and Computer Science
Electrical Engineering

Graph algorithms are concerned with the algorithmic aspects of solving graph problems. The problems are motivated from and have application to diverse areas of computer science, engineering and other disciplines. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for these kinds of graph problems that have at least one of the following properties: the problems involve some type of dynamic updates; the sparsification technique is applicable; or the problems are closely related to communications network issues. The models of parallel computation used in our studies are the Parallel Random Access Machine (PRAM) model and the practical interconnection network models such as meshes and hypercubes. ¶ Consider a communications network which can be represented by a graph G = (V;E), where V is a set of sites (processors), and E is a set of links which are used to connect the sites (processors). In some cases, we also assign weights and/or directions to the edges in E. Associated with this network, there are many problems such as (i) whether the network is k-edge (k-vertex) connected withfixed k; (ii) whether there are k-edge (k-vertex) disjoint paths between u and v for a pair of given vertices u and v after the network is dynamically updated by adding and/or deleting an edge etc; (iii) whether the sites in the network can communicate with each other when some sites and links fail; (iv) identifying the first k edges in the network whose deletion will result in the maximum increase in the routing cost in the resulting network for fixed k; (v) how to augment the network at optimal cost with a given feasible set of weighted edges such that the augmented network is k-edge (k-vertex) connected; (vi) how to route messages through the network efficiently. In this thesis we answer the problems mentioned above by presenting efficient parallel algorithms to solve them. As far as we know, most of the proposed algorithms are the first ones in the parallel setting. ¶ Even though most of the problems concerned in this thesis are related to communications networks, we also study the classic edge-coloring problem. The outstanding difficulty to solve this problem in parallel is that we do not yet know whether or not it is in NC. In this thesis we present an improved parallel algorithm for the problem which needs [bigcircle]([bigtriangleup][superscript 4.5]log [superscript 3] [bigtriangleup] log n + [bigtriangleup][superscript 4] log [superscript 4] n) time using [bigcircle](n[superscript 2][bigtriangleup] + n[bigtriangleup][superscript 3]) processors, where n is the number of vertices and [bigtriangleup] is the maximum vertex degree. Compared with a previously known result on the same model, we improved by an [bigcircle]([bigtriangleup][superscript 1.5]) factor in time. The non-trivial part is to reduce this problem to the edge-coloring update problem. We also generalize this problem to the approximate edge-coloring problem by giving a faster parallel algorithm for the latter case. ¶ Throughout the design and analysis of parallel graph algorithms, we also find a technique called the sparsification technique is very powerful in the design of efficient sequential and parallel algorithms on dense undirected graphs. We believe that this technique may be useful in its own right for guiding the design of efficient sequential and parallel algorithms for problems in other areas as well as in graph theory.

碩士
明新科技大學
資訊管理系碩士班
106
In large networks or multi-processor systems, failure of some nodes may lead to a breakdown of the entire network or system. Thus, to diagnose the faulty nodes in large networks or multi-processor systems plays an extremely important role. The technique of using the test results obtained from the node tests to identify the fault processors in the system is referred to as system-level diagnosis. Thus, diagnosis is exactly a process of discovering the system’s faulty nodes. The effective identification of faulty nodes is critical in reducing the chance of system breakdown and enhancing the stability of information transfer between nodes, which is greatly beneficial to the smoothness of the network system operation. Ye et al. provided a five-round adaptive diagnostic algorithm in IEEE Transactions on Parallel and Distributed Systems in 2015. The algorithm could effectively diagnose the Hamiltonian networks and achieve an almost complete diagnosis. We implemented the Ye et al.’s algorithm into a computer program, and proceeded the five-round adaptive diagnostic program on some recursively constructed networks. In our experiments, the special case of the original algorithm being unable to completely diagnose is further analyzed. Moreover, in-depth analysis on the diagnostic capability of the network is also conducted in some recursively constructed networks by increasing the number of faulty nodes. In 2017, we experimented with hypercubes and obtained relevant analysis results. In this study, we analyzed the relevant results on crossed-cubes and exchanged hypercubes. We compared the performance through the five-round adaptive diagnostic program on these kinds of recursively constructed networks. We found that there is no significant difference in diagnosis ability of the hypercube and the crossed-cube. However, since the number of links of the exchanged hypercube is only about half that of the hypercube or the crossed-cube, the diagnosis ability of the exchanged hypercube is significantly worse than that of the hypercube and the cross cube.

博士
國立成功大學
資訊工程學系碩博士班
97
Design of interconnection networks is an important integral part of the parallel processing or distributed system. There exists mutually con°icting requirements in designed and topology of interconnection networks. It becomes almost impossible for us to design a network which is optimum in all aspects. The hypercube has several excellent proper- ties such as recursive structure, regularity, symmetry, small diameter, low degree, and much small edge complexity, which are very important for designing massively parallel or distributed systems. Furthermore, one variant that has been the focus of great deal of research is the folded hypercube, which is an extension of the hypercube, constructed by adding an edge to every pair of nodes that are the farthest apart, i.e., two nodes with complementary addresses. The folded hypercube has been shown to be able to improve the system's performance over a regular hypercube in many measurements. Paths and cycles, which are two of the most fundamental networks for parallel and distributed computation, are suitable for designing simple algorithms with low commu-nication costs. Paths and cycles can also be used as control/data flow structures for distributed computation in arbitrary networks. An application of paths to a practical problem was encountered in the on-line optimization of a complex flexible manufacturing system. These applications motivate us to embedding paths and cycles in networks. In this dissertation, we consider fault-tolerant path or cycle embedding problems in hypercubes and in folded hypercubes.

博士
國立交通大學
資訊工程研究所
84
The embedding problem has been widely discussed in recent years. In this dissertation, we study embedding of various guest graphs such as complete binary trees, incomplete binary trees, tree machines and quadtrees into host graphs such as hypercubes and incomplete hypercubes. We also study dynamic reconfiguration of complete binary trees in faulty hypercubes. First, we embed a complete binary tree into an incomplete hypercube of the smallest size so that the adjacency of the complete binary tree is preserved, and look for an incomplete binary tree in a hypercube. Second, we optimally embed a large complete binary tree into a hypercube of limited size. Third, we embed a tree machine into an incomplete hypercube with expansion 1, and embed a large tree machine into a hypercube of limited size with load-balance. Fourth, we embed a quadtree into a hypercube so that the adjacency of the quadtree is preserved, and embed a quadtree into an incomplete hypercube with expansion 1. Fifth, we dynamically reconfigure to embed a complete binary tree into a faulty hypercube, and the number of the affected nodes of the complete binary tree are as few as possible after reconfiguring.

碩士
國立交通大學
資訊科學學系
84
We propose and analyze some variation of the uni-directional interconnection network topology. The Foled Uni-directional Hyperbues are new topologies obtainedby adding some extra links from the uni-directional hyperbues(UHCs).We also derive the one to one routing algorithms and analyze its average distanceby computer. The diameter of these network topologies is better than thatof UHC.Thus, a better structure is suggested for applying to the Metropolitan Area Network(MANs).

by D.P. Bertsekas ... [et al.].
Cover title.
Includes bibliographical references.
Supported by NSF with matching funds from Bellcore, Inc. ECS-8519058 ECS-8552419 Supported by the ARO. DAAL03-86-K-0171 Supported by the AFOSR. AFOSR-88-0032

碩士
明新科技大學
資訊管理研究所
99
The cycle embedding problem in interconnection networks is an important issue, because it is one of measurements for determining whether the topology of a network is suitable for an application in which embedding rings of various lengths into the topology is required. Embedding cycles of different sizes into a network are benefit to execute parallel programs efficiently. The folded hypercube is a popular network because of its attractive properties. Given an n-dimensional folded hypercube FQn and let e be any edge of FQn. In this paper, we discuss the number of simple k-cycles in FQn, which passing through the edge e, for k = 4, 6.

碩士
國立新竹教育大學
應用數學系碩士班
100
Abstract In this research we construct all non-isomorphic paths in the n-dimensional hypercube, and count the number of them. As the dimension n gets higher, the amount of the paths increases extremely large. So a normal algorithm cannot handle this situation. That is why we need to design a new method to construct and search non-isomorphic paths. This thesis offers an efficient algorithm to construct and search non-isomorphic paths. Two computer programs for solving the same problem are given here by using two different data structures. Both of them are programming by C.

博士
淡江大學
資訊工程學系博士班
94
The hypercube is a widely-used interconnection architecture in the parallel machine. The Incrementally Extensible Hypercube (IEH), which is derived from the hypercube, is a generalization of interconnection network. Unlike the hypercube, the IEH can be constructed for any number of nodes. In other words, the IEH is incrementally expandable. In this thesis, the problem of embedding and reconfiguring some regular structures is considered in an IEH with faulty nodes. In recent years, the Fibonacci cube is a new interconnection architecture derived from hypercube. It also has some properties differ from hypercube. Thus we discuss the embedding of Fibonacci cube into the faulty hypercube. Some fault-tolerant embedding algorithms are proposed in this thesis. First, the algorithm in the present study enables us to obtain the good embedding of a ring into a faulty IEH with 2-expansion. Such result can be tolerated up to (n+1) faults with congestion 1, load 1, and dilation 3. When we allow unbounded expansion, the result of embedding of a ring into a faulty IEH can be tolerated up to O(n*log2m) faults with congestion 1, load 1, and dilation 4. The embedding methods in the study are mainly optimized for balancing the processor loads, under the situation of minimizing dilation and congestion as far as possible. Next we consider embedding of mesh into faulty IEH. In 2-expansion, it can be tolerated (n+1) faults with dilation 3, congestion 1, and load 1. Moreover, it can be tolerated up to O(n2-(r+s)2) in unbounded expansion. We discuss embedding of a complete binary tree into faulty IEH in the third. The cost is dilation 4, congestion 1, and load 1. In 2-expansion and unbounded expansion, embedding of a complete binary tree into faulty IEH can be tolerated (n+1) and O(n2-h2) faults. Finally, embedding of Fibonacci cube into faulty hypercube with dilation 3, congestion 2, load 1, unbounded expansion and O(m2-n2) faults can be tolerated, induced by our algorithm.

碩士
明新科技大學
資訊管理系碩士班
105
The diagnosis of faulty nodes in large networks or multi-processor systems plays an extremely important role. The technique of using the test results obtained from the node tests to identify the fault processors in the system is referred to as system-level diagnosis. The failure of some nodes in large networks or multi-processor systems could lead to a breakdown of the entire network or system. Thus, diagnosis is exactly a process of discovering the system’s faulty nodes. The effective identification of faulty nodes is critical in reducing the adverse factors of the network architecture and enhancing the stability of information transfer between nodes, which is greatly beneficial to the smoothness of the network system operation. Ye et al. provided a five-round adaptive diagnostic algorithm in IEEE Transactions on Parallel and Distributed Systems in 2015. The algorithm could effectively diagnose the Hamiltonian networks and achieve an almost complete diagnosis. The present study realizes the Ye et al.’s algorithm, where the special case of the original algorithm being able to completely diagnose is further analyzed. An in-depth analysis on the diagnostic capability of the network is also conducted in the 5-D and 6-D hypercubes by increasing the number of faulty nodes.

碩士
大葉大學
資訊工程學系碩士班
97
Let G = (V, E) be a graph. For any two vertices u, v Î V(G), a cycle C is called (u,v)-geodesic if there exists a u-v shortest path of G lying on C. A bipartite graph G is called geodesic bipancyclic if for any two vertices u, v Î V, there exists a (u,v)-geodesic cycle of every even length ranging from max{2d(u, v), 4} to |V|. In this thesis, we first show that the hypercube Qn for n  4 is geodesic bipancyclic when it has two adjacent fault vertices. Then we prove that Qn is 2-disjoint geodesic bipancyclicity for n  4. That is, given any four vertices u, v, x, y without forming u, x, v, u, y, v, x, u, y, x, v, y paths, and given any even integers l1, l2 such that l1 + l2  2n, l1  min{2d(u, v) + 2, 2n}, and l2  min{2d(x, y) + 2, 2n}, there exist two disjoint cycles C1 and C2 in Qn such that C1 is a (u, v)-geodesic cycle of length l1, and C2 is a (x, y)-geodesic cycle of length l2.

碩士
國立交通大學
資訊科學與工程研究所
94
Xu et al. showed that for any set of faulty edges F of an n-dimensional hypercube Qn with |F|≦n-1, each edge of Qn-F lies on a cycle of every even length from 6 to 2n, n≧4, provided not all edges in F are incident with the same vertex. In this paper, we find that under similar condition, the number of faulty edges can be much greater and the same result still holds. More precisely, we show that, for up to |F|=2n-5 faulty edges, each edge of the faulty hypercube Qn-F lies on a cycle of every even length from 6 to 2n with each vertex having at least two healthy edges adjacent to it, for n≧3. Moreover, this result is optimal in the sense that the result can not be guaranteed, if there are 2n-4 faulty edges.

碩士
南台科技大學
資訊管理系
92
The problems of embedding trees into hypercubes have attracted considerable attention in the literature for the past 20 years. Especially, many researches were devoted to the problem of embedding binary trees into hypercubes. Hypercubes are very important interconnection networks because they own many good topological properties such as recursiveness, symmetry, small diameter, and fault-tolerant capability. Besides, hypercubes have been implemented as commercial computers. On the other hand, binary trees are the one of the most important topologies since many efficient algorithms can be executed on them. Embedding binary trees into hypercubes will make these efficient algorithms of trees easily transfer to commercial hypercube-computers. In this paper, we improve Chen and Stallmann’s previous work and propose a new recursive algorithm to embed arbitrary binary trees into hypercubes. In general cases, the dilation of our embedding algorithm will be smaller than or equal to the dilation of Chen and Stallmann. Keyword：binary tree, diameter, dilation, embedding, Gray code, hypercube, preorder traversal, recursiveness, symmetry

博士
國立中央大學
數學研究所
94
Let G be a graph with connectivity κ(G). It follows from Menger's Theorem that there are k vertex-disjoint paths joining any two distinct vertices when k ≦κ(G). A k -container C ( u, v) of a graph G is a set of k vertex-disjoint paths between u and v. A k-container is a k*-container if it contains all vertices of G . A graph G is k*-connected if there exists a k*-container between any two vertices. A graph G is super spanning connected if G is k*-connected for every 1 ≦ k ≦κ(G). However, we need some modification as we study bipartite k-connected graphs. A bipartite graph G is k*-laceable if there exists a k*-container between any two vertices from different partite sets. A bipartite graph G is super spanning laceable if G is k*-laceable for 1 ≦ k ≦ κ(G). A k*-container C ( u, v) ={ P1, … , Pk } is equitable if | | Pi | - | Pj | | ≦ 2, 1 ≦ i , j ≦ k. The hypercube Qn is one of the most popular networks. In this thesis, we will discuss that the spanning connectivity, the spanning laceability, and related problems of hypercube Qn, folded hypercube FQn, and enhanced hypercube Qn,m.

碩士
明新科技大學
資訊管理研究所
99
The underlying topology of an interconnection network is usually modeled as a graph G = (V,E), in which V is the vertex set and E is the edge set. A graph G is pancyclic if any k-cycle can be embedded into it for 3 ≤ k ≤ |V(G)|; G is bipancyclic if any k-cycle of even length can be embedded into it for 4 ≤ k ≤ |V(G)|. The hypercube is a popular network and it has been widely used in parallel systems. It also has many attractive properties, including regularity, symmetry, small diameter, strong connectivity, recursive construction, partition ability, relatively low link complexity, and easy routing and broadcasting algorithms. The cycle embedding problem is one of the most popular research issues in interconnection networks, because it is an important measurement for determining whether the topology of a network is suitable for an application in which embedding rings of various lengths into the topology is required. Moreover, embedding cycles of different sizes into a network are benefit to execute parallel programs efficiently. There are many literatures which discussing cycle embedding of various lengths. Let edge e be any edge of the hypercube Qn . In this proposal, we discuss the number of simple k-cycles, which passing through the edge e for k = 4, 6, and 8 in the hypercube Qn .

碩士
淡江大學
電機工程學系
89
Title of Thesis: Constructing Fault-Tolerant Communication Total pages: 92 Trees for Hypercubes Key words: Hypercubes, fault-tolerance, faulty links, fault-tolerant communication trees, distributed approaches, maximal fault-free subcubes. Name of Institute: Department of Electrical Engineering, Tamkang University Graduate date: June, 2001 Degree conferred: Master Name of student: Shih-Yuan Chen Advisor: Dr. Po-Jen Chuang 陳 世 元 莊 博 任 博士 Abstract: A hypercube system can construct a non-faulty communication tree even if some faulty links exist in the system. Since the faulty links are randomly distributed, the faulty links may still exist in the communication tree when there are many faulty links. Consequently, sending data messages through neighboring nodes is necessary in such a situation. We propose a fault-tolerant scheme for improving the success rate of sending data messages through neighboring nodes. The scheme improves the fault-tolerant capability efficiently with a little added time complexity. In the previous related research, a node is first selected as the root and a fault-tolerant communication tree is then constructed in a non-distributed way. In this research, we present a distributed approach able to construct a fault-tolerant communication tree with lower time complexity. By this approach, a maximal fault-free subcube by using our proposed algorithms is found first and all nodes of the fault-free subcube are considered to be subroots. Then the fault-tolerant communication subtrees from the subroots can be constructed in a distributed way. Fault-tolerant communication trees can be successfully constructed as in the non-distributed way for all of the subroots so selected. As a result, the distributed approach not only speeds up the fault-tolerant communication tree construction but also improves the performance and keeps the original fault-tolerant capability.

博士
國立臺灣大學
資訊工程研究所
81
Large-scale, general-purpose multicomputers with interconnect- ion networks have been a trend for high-speed computing. Undoub- tedly, fast data communication is a key to achieve high perform- ance of such machines. Because many factors that interact with each other are involved, data communication problems on multico- mputers are characterized by their inherent versatility, comple- xity and difficulty. As a result, they pose a high challenge on designing efficient communication algorithms even for special classes of message patterns. A broad class of messge patterns which are important in multi- computers can be represented in the (s, d)-mask formalism. It contains abundant communication patterns, including homogeneous and inhomogeneous ones. Accordingly, studying the communication problem for (s, d)-masks will expose some deep insights into the general communication problems on multicomputers. In this thesis we use a transformational approach to contemplate the communica- tion problem for (s, d)- mask patterns in the popular hypercube network. Based on this approach, a general scatter-concentrate routing scheme is proposed, which in turn results in many effic- ient or even optimal algorithms for the message patterns with varied message lengths in single-port and all-port hypercubes. Besides, many insights into the effects of multi-path routing on the communication performance emerge in the course of study.