Parallel computing has long been an area of research interest because exploiting parallelism in difficult problems has promised to deliver orders of magnitude speedups. Processors are now both powerful and cheap, so that systems incorporating tens, hundreds or even thousands of powerful processors need not be prohibitively expensive. The weak link in exploiting parallelism is the means of communication between the processors. Shared memory systems are fundamentally limited in the number of processors they can utilise. To achieve high levels of parallelism it is still necessary to use distributed memory and some form of interconnection network. But interconnection networks can be costly, slow, difficult to build and expand, vulnerable to faults and limited in the range of problems they can be used to solve effectively. As a result there has been extensive research into developing interconnection networks which overcome some or all of these difficulties. In this thesis it is argued that a new interconnection network, Hierarchical Cliques (HiC), and a derivative, FatHiC, possesses many desirable properties and are worthy of consideration for use in building parallel computers. A fundamental element of an interconnection network is its topology. After defining the topology of HiC, expressions are derived for the various parameters which define its underlying limits of performance and fault tolerance. A second element of an interconnection network is an addressing and routing scheme. The addressing scheme and routing algorithms of HiC are described. The flexibility of HiC is demonstrated by developing embeddings of popular, regular interconnection networks. Some embeddings into HiC suffer from high congestion, however the FatHiC network is shown to have low congestion for those embeddings. The performance of some important, regular, data parallel problems on HiC and ++ / FatHiC are determined by analysis and simulation, using the 2D-mesh as a means of comparison. But performance alone does not tell the whole story. Any parallel computer system must be cost effective. In order to analyse the cost effectiveness of HiCs an existing measure was expanded to provide a more realistic model and a more accurate means of comparison. One aim of this thesis is to demonstrate the suitability of HiC for parallel computing systems which execute irregular algorithms requiring dynamic load balancing. A new dynamic load balancing algorithm is proposed which takes advantage of the hierarchical structure of the HiC to reduce communication overheads incurred when distributing work. To demonstrate performance of an irregular problem, a novel parallel algorithm was developed to detect subgraph isomorphism from many model graphs to a single input graph. The use of the new load balancing algorithm in conjunction with the subgraph isomorphism algorithm is discussed.

Submitted by Marcos Grilo Rosa (grilo@uefs.br) on 2017-01-05T19:11:59Z No. of bitstreams: 1 tesevsfinalMarcosGrilo.pdf: 11311408 bytes, checksum: 3ce07aff3fe0fb9dc534e80e667eeb5b (MD5) / Rejected by Maria Auxiliadora da Silva Lopes (silopes@ufba.br), reason: Prezado Marcos, Favor registrar os nomes completos dos participantes da banca; inserir o "abstract" e as "key words". Saudações, Maria Auxiliadora Lopes UFBA/Faced/Biblioteca on 2017-01-09T14:10:18Z (GMT) / Submitted by Marcos Grilo Rosa (grilo@uefs.br) on 2017-01-09T17:16:07Z No. of bitstreams: 1 tesevsfinalMarcosGrilo.pdf: 11311408 bytes, checksum: 3ce07aff3fe0fb9dc534e80e667eeb5b (MD5) / Approved for entry into archive by Maria Auxiliadora da Silva Lopes (silopes@ufba.br) on 2017-01-19T14:35:53Z (GMT) No. of bitstreams: 1 tesevsfinalMarcosGrilo.pdf: 11311408 bytes, checksum: 3ce07aff3fe0fb9dc534e80e667eeb5b (MD5) / Made available in DSpace on 2017-01-19T14:35:53Z (GMT). No. of bitstreams: 1 tesevsfinalMarcosGrilo.pdf: 11311408 bytes, checksum: 3ce07aff3fe0fb9dc534e80e667eeb5b (MD5) / No campo da inteligência artificial, redes semânticas são utilizadas para a representação de conhecimento e processamento de linguagem natural. Redes semânticas são sistemas de representação do conhecimento baseados em grafos cujos vértices são palavras e as arestas, os relacionamentos entre as palavras estabelecidos por alguma regra. Lidar com redes semânticas é uma atividade bastante complicada, principalmente, quando se manipula redes com milhares de palavras. Conjecturamos a possibilidade de se representar uma dada rede semântica baseada em títulos de artigos de periódicos científicos (RST) por meio de uma RST uniforme, de modo que esta possua a mesma estrutura topológica e reflita o vocabulário da RST original. O problema da nossa tese consiste em saber qual o menor tamanho de uma RST uniforme que pode ser obtida de uma dada RST. Esta pesquisa visa determinar o ponto crítico no qual ocorre uma mudança topológica de uma RST de modo que a rede obtida reflita o vocabulário da RST original. Realizamos um experimento que consistiu em submeter RST a estratégias de remoção de vértices. Os resultados apontam a existência de uma fração fp de vértices removidos aleatoriamente e uniformemente que mantém a estrutura topológica e reflita o vocabulário da RST original. Desta forma, RST podem ser representadas por RST uniformes mínimas. A representação do conhecimento é determinante em processos e cientes de busca de informações e difusão de conhecimento. Ademais, RST uniformes mínimas poderão auxiliar pesquisadores na busca mais e ciente de temas relacionados ao seu objeto de investigação. / Abstract In the field of artificial intelligence, semantic networks are used for knowledge representation and natural language processing. Semantic networks are graph-based knowledge representation systems whose vertices are words and edges, relationships between words set by a rule. Dealing with semantic networks is a very complicated activity, mainly, when it handles networks with thousands of words. We conjecture the possibility of representing a given semantic network based on titles of scientific papers (RST) by a uniform RST, so that this has the same topological structure and reflect the vocabulary of the original RST. The problem of our thesis is to know what a uniform smaller RST can be obtained from a given RST. This study aims to determine the critical point at which there is a topological change of a RST so that the network obtained reflect the vocabulary of the original RST. We conducted an experiment that it consists to submit RST removing vertices strategies. The results indicate the existence of a fraction fp vertices removed randomly and evenly preserving the topological structure and reflect the vocabulary of the original RST. Thus, RST may be represented by minimum uniform RST. The representation of knowledge is determinant in efficient processes search of information and diffusion of knowledge. In addition, minimum uniform RST can assist researchers in the most efficient search issues related to its investigation.