482 research outputs found
Interconnection networks for parallel and distributed computing
No full textParallel computers are generally either shared-memory machines or distributed- memory machines. There are currently technological limitations on shared-memory architectures and so parallel computers utilizing a large number of processors tend tube distributed-memory machines. We are concerned solely with distributed-memory multiprocessors. In such machines, the dominant factor inhibiting faster global computations is inter-processor communication. Communication is dependent upon the topology of the interconnection network, the routing mechanism, the flow control policy, and the method of switching. We are concerned with issues relating to the topology of the interconnection network. The choice of how we connect processors in a distributed-memory multiprocessor is a fundamental design decision. There are numerous, often conflicting, considerations to bear in mind. However, there does not exist an interconnection network that is optimal on all counts and trade-offs have to be made. A multitude of interconnection networks have been proposed with each of these networks having some good (topological) properties and some not so good. Existing noteworthy networks include trees, fat-trees, meshes, cube-connected cycles, butterflies, Möbius cubes, hypercubes, augmented cubes, k-ary n-cubes, twisted cubes, n-star graphs, (n, k)-star graphs, alternating group graphs, de Bruijn networks, and bubble-sort graphs, to name but a few. We will mainly focus on k-ary n-cubes and (n, k)-star graphs in this thesis. Meanwhile, we propose a new interconnection network called augmented k-ary n- cubes. The following results are given in the thesis.1. Let k ≥ 4 be even and let n ≥ 2. Consider a faulty k-ary n-cube Q(^k_n) in which the number of node faults f(_n) and the number of link faults f(_e) are such that f(_n) + f(_e) ≤ 2n - 2. We prove that given any two healthy nodes s and e of Q(^k_n), there is a path from s to e of length at least k(^n) - 2f(_n) - 1 (resp. k(^n) - 2f(_n) - 2) if the nodes s and e have different (resp. the same) parities (the parity of a node Q(^k_n) in is the sum modulo 2 of the elements in the n-tuple over 0, 1, ∙∙∙ , k - 1 representing the node). Our result is optimal in the sense that there are pairs of nodes and fault configurations for which these bounds cannot be improved, and it answers questions recently posed by Yang, Tan and Hsu, and by Fu. Furthermore, we extend known results, obtained by Kim and Park, for the case when n = 2.2. We give precise solutions to problems posed by Wang, An, Pan, Wang and Qu and by Hsieh, Lin and Huang. In particular, we show that Q(^k_n) is bi-panconnected and edge-bipancyclic, when k ≥ 3 and n ≥ 2, and we also show that when k is odd, Q(^k_n) is m-panconnected, for m = (^n(k - 1) + 2k - 6’ / ‘_2), and (k -1) pancyclic (these bounds are optimal). We introduce a path-shortening technique, called progressive shortening, and strengthen existing results, showing that when paths are formed using progressive shortening then these paths can be efficiently constructed and used to solve a problem relating to the distributed simulation of linear arrays and cycles in a parallel machine whose interconnection network is Q(^k_n) even in the presence of a faulty processor.3. We define an interconnection network AQ(^k_n) which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube Q(^k_n) has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube Q(^k_n) - is a Cayley graph (and so is vertex-symmetric); has connectivity 4n - 2, and is such that we can build a set of 4n - 2 mutually disjoint paths joining any two distinct vertices so that the path of maximal length has length at most max{{n- l)k- (n-2), k + 7}; has diameter [(^k) / (_3)] + [(^k - 1) /( _3)], when n = 2; and has diameter at most (^k) / (_4) (n+ 1), for n ≥ 3 and k even, and at most [(^k)/ (_4) (n + 1) + (^n) / (_4), for n ^, for n ≥ 3 and k odd.4. We present an algorithm which given a source node and a set of n - 1 target nodes in the (n, k)-star graph S(_n,k) where all nodes are distinct, builds a collection of n - 1 node-disjoint paths, one from each target node to the source. The collection of paths output from the algorithm is such that each path has length at most 6k - 7, and the algorithm has time complexity O(k(^3)n(^4))
N-ary decomposition for multi-class classification
No full text© 2019, The Author(s), under exclusive licence to Springer Science+Business Media LLC, part of Springer Nature. A common way of solving a multi-class classification problem is to decompose it into a collection of simpler two-class problems. One major disadvantage is that with such a binary decomposition scheme it may be difficult to represent subtle between-class differences in many-class classification problems due to limited choices of binary-value partitions. To overcome this challenge, we propose a new decomposition method called N-ary decomposition that decomposes the original multi-class problem into a set of simpler multi-class subproblems. We theoretically show that the proposed N-ary decomposition could be unified into the framework of error correcting output codes and give the generalization error bound of an N-ary decomposition for multi-class classification. Extensive experimental results demonstrate the state-of-the-art performance of our approach
Prefixless q-ary Balanced Codes with Fast Syndrome-Based Error Correction
No full textWe investigate a Knuth-like scheme for balancing q-ary code words, which has the virtue that lookup tables for coding and decoding the prefix are avoided by using precoding and error correction techniques. We show how the scheme can be extended to allow for error correction of single channel errors using a fast decoding algorithm that depends on syndromes only, making it considerably faster compared with the prior art exhaustive decoding strategy. A comparison between the new and prior art schemes, both in terms of redundancy and error performance, completes the study.Accepted Author ManuscriptDiscrete Mathematics and Optimizatio
Efficient Balancing Techniques for q-ary Codes with Error Correction Capabilities
No full textThis document aims to explore charge balancing methods, with error correction capabilities for q-ary sequences, and to develop new techniques or to extend previous ones. The problem is approached by using analytical as well as simulation tools.Telecommunications & Sensing SystemsIntelligent SystemsElectrical Engineering, Mathematics and Computer Scienc
Robust Plackett–Luce model for k-ary crowdsourced preferences
No full text© 2017, The Author(s). The aggregation of k-ary preferences is an emerging ranking problem, which plays an important role in several aspects of our daily life, such as ordinal peer grading and online product recommendation. At the same time, crowdsourcing has become a trendy way to provide a plethora of k-ary preferences for this ranking problem, due to convenient platforms and low costs. However, k-ary preferences from crowdsourced workers are often noisy, which inevitably degenerates the performance of traditional aggregation models. To address this challenge, in this paper, we present a RObust PlAckett–Luce (ROPAL) model. Specifically, to ensure the robustness, ROPAL integrates the Plackett–Luce model with a denoising vector. Based on the Kendall-tau distance, this vector corrects k-ary crowdsourced preferences with a certain probability. In addition, we propose an online Bayesian inference to make ROPAL scalable to large-scale preferences. We conduct comprehensive experiments on simulated and real-world datasets. Empirical results on “massive synthetic” and “real-world” datasets show that ROPAL with online Bayesian inference achieves substantial improvements in robustness and noisy worker detection over current approaches
Linear complexity profile of m-ary pseudorandom sequences with small correlation measure
No full textAbstractWe estimate the linear complexity profile of m-ary sequences in terms of their correlation measure, which was introduced by Mauduit and Sárközy. For prime m this is a direct extension of a result of Brandstätter and the second author. For composite m, we define a new correlation measure for m-ary sequences, relate it to the linear complexity profile and estimate it in terms of the original correlation measure. We apply our results to sequences of discrete logarithms modulo m and to quaternary sequences derived from two Legendre sequences
Medical Image Watermarking Technique in the Application of E- diagnosis Using M-Ary Modulation
No full textAbstractA robust and lossless ROI medical image watermarking technique using M-Ary modulation is proposed in this paper. The system's effectiveness is experimentally tested for two different medical image modalities of brain using various quality measures as payload, PSNR, MSE and SSIM. The proposed algorithm provides high robustness, higher PSNR and low relative entropy distance as a criterion for protection
Communication system with M-ary chirp modulation
No full textCílem této diplomové práce je experimentální softwarové realizace komunikačního
systému pracujícím v reálném čaše. Diplomová práce navazuje na [4], kde autor
vytvořil v prostředí MATLAB softwarové řešení modulátoru a demodulátoru s využitím
modulace vícestavových rozmítaných modulací. Tato práce poukazuje na problémy
původní verze a popisuje následné řešení a vylepšení.
Značné úsilí bylo vyvinuto pro snížení výpočetního výkonu. To vedlo k novým
neobvyklým možnostem demodulačního procesu, kdy se využila decimace a frakční
Fourierova transformace.
Výsledkem této práce je funkční softwarový prototyp komunikačního systému se
schopností volit energetickou nebo spektrální účinnost pro skupinu vícestavových
rozmítaných modulací, který byl vytvořen v softwarovém prostředí MATLABObhájenoThe aim of this thesis is the experimental software implementation of a communication
system working in real-time. Thesis follows up on [4], where author created software solution
of the modulator and demodulator utilizing M-ary chirp modulation in a MATLAB
environment. This paper points out to the issues of the original version and describes
subsequent solutions and improvements. In particular, significant eort to decrease computation
difficulty has been made. This lead to new unusual possibilities to demodulation
process, where decimation and fractional Fourier Transform were utilized.
The result of this thesis is a functional software prototype of the communication
system, with an ability to select energy or spectral efficiency over a group of the M-ary
chip modulation, created in the MATLAB environment
Stagewise learning for noisy k-ary preferences
No full text© 2018, The Author(s). The aggregation of k-ary preferences is a novel ranking problem that plays an important role in several aspects of daily life, such as ordinal peer grading, online image-rating, meta-search and online product recommendation. Meanwhile, crowdsourcing is increasingly emerging as a way to provide a plethora of k-ary preferences for these types of ranking problems, due to the convenience of the platforms and the lower costs. However, preferences from crowd workers are often noisy, which inevitably degenerates the reliability of conventional aggregation models. In addition, traditional inferences usually lead to massive computational costs, which limits the scalability of aggregation models. To address both of these challenges, we propose a reliable CrowdsOUrced Plackett–LucE (COUPLE) model combined with an efficient Bayesian learning technique. To ensure reliability, we introduce an uncertainty vector for each crowd worker in COUPLE, which recovers the ground truth of the noisy preferences with a certain probability. Furthermore, we propose an Online Generalized Bayesian Moment Matching (OnlineGBMM) algorithm, which ensures that COUPLE is scalable to large-scale datasets. Comprehensive experiments on four large-scale synthetic datasets and three real-world datasets show that, COUPLE with OnlineGBMM achieves substantial improvements in reliability and noisy worker detection over other well-known approaches
Response to Shayah and Coatesworth
No full textFull assessment of snoring should involve general and local factors which contribute to the patient's complaint, such as any history of apnoea attacks, high body mass index, reflux, smoking, alcohol consumption, uvulasize and laxity of soft palate, collar size and base of tongue. The paper did not clearly identify the potential importance of these factors
- …
