Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n×n binary image on the Bulk-Synchronous Parallel(BSP)model. The BSP model is an asynchronous parallel computing model, where its communication features are abstracted by two parameters L and g: L denotes synchronization periodicity and g denotes a reciprocal of communication bandwidth. We propose two parallel algorithms for the all nearest neighbor problems based on two distance metrics. The first algorithm is for L_p distance, and the second algorithm is for weighted distance. Both two algorithms run in O((n?2) / p+L)computation time and in O(gn / √<p>+L)communication time using p(1≤p≤n)processors and in O((n?2) / p+(d+L)(log p / n) / (log(d+1)))computation time and in O(g n / √<p>+(gd+L)(log p / n) / (log(d+1)))communication time using p(n<p≤n?2)processors on the BSP model, for any integer d(1≤d≤p / n)

• 社団法人電子情報通信学会の論文
• 2000-02-25

著者

• Fujiwara Hideo

  The Authors Are With The Graduate School Of Information Science Nara Institute Of Science And Techno

• Inoue M

  Graduate School Of Information Science Nara Institute Of Science And Technology

• FUJIWARA Hideo

  the Graduate School of Information Science, Nara Institute of Science and Technology

• Fujiwara Hideo

  Naist

• Fujiwara Hideo

  Graduate School Of Infromation Science Nara Institute Of Science And Technology (naist)

• Fujiwara Hideo

  Nara Institute Of Science And Technology

• MASUZAWA Toshimitsu

  the Graduate School of Information Science and Technology, Osaka University

• INOUE Michiko

  the Graduate School of Information Science, Nara Institute of Science and Technology(NAIST)

• ISHIMIZU Takashi

  The Graduate School of Information Science, Nara Institute of Science and Technology

• FUJIWARA Akihiro

  The Department of Computer Science and Electronics, Kyushu Institute of Technology

• Masuzawa Toshimitsu

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Masuzawa Toshimitsu

  Nara Institute Of Sciences And Technology

• Masuzawa Toshimitsu

  The Graduate School Of Information Science And Technology Osaka University

• Masuzawa Toshimitsu

  Department Of Computer Science Graduate School Of Information Science And Technology Osaka Universit

• Fujiwara Hideo

  The Graduate School Of Information Science Nara Institute Of Science And Technology

• Fujiwara H

  Nara Inst. Sci. And Technol. Kansai Science City Jpn

• Fujiwara A

  Ntt Docomo Inc. Yokosuka‐shi Jpn

• Inoue Michiko

  The Graduate School Of Information Science Nara Institute Of Science And Technology(naist)

• Ishimizu Takashi

  The Graduate School Of Information Science Nara Institute Of Science And Technology

関連論文

• Classification of Sequential Circuits Based on τ^k Notation and Its Applications(VLSI Systems)
• Fault-Tolerant and Self-Stabilizing Protocols Using an Unreliable Failure Detector
• B-5-152 Impact of EDCA Parameters on Throughput Improvement in Layer-2 Mesh Networks with Hidden Terminal Problems
• B-5-151 EDCA Based Congestion Control Method for WLAN Mesh Networks
• Experimental Evaluation of Adaptive Contention Window Control for Layer-2 Mesh Networks
• Performance Evaluation of Mesh Network using Multi Frequency Bands
• Enhancement of Mesh Network Oriented IEEE802.11 MAC Protocol
• Performance Evaluation of Mesh Network using Multi Frequency Bands
• Enhancement of Mesh Network Oriented IEEE802.11 MAC Protocol
• B-5-250 Fairness Improvement by Enhanced IEEE802.11 MAC Protocol in Wireless Mesh Network
• B-5-249 Enhancement of Mesh Network Oriented IEEE802.11 MAC Protocol
• On the Effect of Scheduling in Test Generation
• Testing for the Programming Circuit of SRAM-Based FPGAs
• Analysis of Test Generation Complexity for Stuck-At and Path Delay Faults Based on τ^k-Notation(Complexity Theory)
• A DFT Selection Method for Reducing Test Application Time of System-on-Chips(SoC Testing)(Test and Verification of VLSI)
• A Test Plan Grouping Method to Shorten Test Length for RTL Data Paths under a Test Controller Area Constraint(Test)(Dependable Computing)
• A Test Plan Grouping Method to Shorten Test Length for RTL Data Paths under a Test Controller Area Constraint
• Design for Two-Pattern Testability of Controller-Data Path Circuits
• Analyzing Path Delay Fault Testability of RTL Data Paths:A Non-Scan Approach (デザインガイヤ2000) -- (VLSIの設計/検証/テスト及び一般)
• Analyzing Path Delay Fault Testability of RTL Data Paths: A Non-Scan Approach (デザインガイヤ2000) -- (VLSIの設計/検証/テスト及び一般)
• Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults(Foundations of Computer Science)
• Delay Fault Testing of Processor Cores in Functional Mode(Dependable Computing)
• Wait-Free Linearizable Distributed Shared Memory
• Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model
• High-Level Synthesis for Weakly Testable Data Paths(Special Issue on Test and Diagnosis of VLSI)
• A Simple Parallel Algorithm for the Medial Axis Transform (Special Issue on Architectures Algorithms and Networks for Massively parallel Computing)
• A Parallel Method for the Prefix Convex Hulls Problem
• Distributed Leader Election on Chordal Ring Networks
• Positron Annihilation in Nearly Perfect Crystals of Aluminum during Slow Cooling
• Performance Analysis of Parallel Test Generation for Combinational Circuits
• Optimal Granularity of Parallel Test Generation on the Client-Agent-Server Model
• Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model(Parallel and Distributed Computing,Foundations of Computer Science)
• Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
• SPIRIT:A High Robust Combinational Test Generation Algorithm (デザインガイヤ2000) -- (VLSIの設計/検証/テスト及び一般)
• A Self-Stabilizing Spanning Tree Protocol that Tolerates Non-quiescent Permanent Faults
• Fault-Tolerance of Distributed Algorithms : Self-Stabilization and Wait-Freedom(Special Issue on Algorithm Engineering : Surveys)
• A Non-scan DFT Method at Register-Transfer Level to Achieve 100% Fault Efficiency (特集:システムLSIの設計技術と設計自動化)
• Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
• Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System(Special Section on Discrete Mathematics and Its Applications)
• Non-scan Design for Testability for Synchronous Sequential Circuits Based on Fault-Oriented Conflict Analysis(Fault Tolerance)
• Non-scan Design for Testability for Synchronous Sequential Circuits Based on Fault-Oriented Conflict Analysis
• Test Pattern Ordering and Selection for High Quality Test Set under Constraints

もっと見る 閉じる

スポンサーリンク