Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
並列処理に関するyou21979のブックマーク (16)
-
you21979 2014/06/04
-
-
Bulk synchronous parallel - Wikipedia
The bulk synchronous parallel (BSP) abstract computer is a bridging model for designing parallel algorithms. It is similar to the parallel random access machine (PRAM) model, but unlike PRAM, BSP does not take communication and synchronization for granted. In fact, quantifying the requisite synchronization and communication is an important part of analyzing a BSP algorithm. The BSP model was devel
-
直列加算と並列加算でdoubleの足し算の結果が変わる話 - きしだのHatena
Javaに限った話ではないのだけど、Javaで並列加算が気軽にできるようになったので、気に留めておいたほうがいい話。 まず、次のようなコードを動かしてみます。 public static void main(String[] args){ double[] data = { 1.234E80, -1.234E80, 2, 3}; System.out.println(Arrays.stream(data).sum()); System.out.println(Arrays.stream(data).parallel().sum()); } 1.234×10^80と-1.234×10^80という、桁が大きくて符号の違う数を並べて、そのあとに2と3という1桁の数値を置いています。 これらを加算すると、1.234×10^80と-1.234×10^80は符号が違うだけなので、当然結果は0になります
-
Linda - Wikipedia
この項目では、プログラミング言語の「Linda」について説明しています。その他の用法については「リンダ (曖昧さ回避)」をご覧ください。 並列処理とプログラミング言語の関わりを考えたとき、いくつかの手法が考えられる。まず、言語を並列処理向きに一から設計する手法である。例えば、CSPに基づいた Occam などがある。第二に既存の言語に並列処理モデルを導入して新たな言語を構築する手法である。例えば、Multilisp、Concurrent Smalltalk などがある。第三に並列化を言語仕様とは別の部分で実現する手法である。例えば、コンパイラによって並列処理を実現する。 Linda はこれらとは異なるアプローチであり、既存の言語仕様に修正を加えずに協調モデル（coordination model）を付加することで並列処理を実現する。このため Linda は「協調言語（coordinatio
-
コンピュータサイエンス史上最大の課題「並列処理による性能向上」～情報処理学会創立50周年記念全国大会の招待講演
「いま、並列処理の壁というコンピュータサイエンス史上最大の課題に直面しています。しかしこれはチャンスでもあります。新しい時代を切り開いていきましょう」。IBM名誉フェローのFran Allen氏は、昨日3月10日に行われた日本の情報処理学会創立50周年記念全国大会の招待講演の演壇からこんなメッセージを聴衆に投げかけました。 Fran Allen氏は、コンパイラやプログラミング言語が専門で、女性で初めてチューリング賞を受賞した人。今回の招待講演のためにわざわざ来日したと紹介されました。 講演のタイトルは「The Challenge of the Multicores」。ここからは、Allen氏の講演の内容を紹介しましょう。 （この講演は英語で行われたものです。内容にはできるだけ正確を期したつもりですが、理解不足のところや聞き取れなかったところもありました。もし誤解や不正確なところがありました
-
インテルTBBから学ぶループの並列化
はじめに この連載では、並列処理を高度に抽象化したインテルTBBを通じて、並列化の考え方を取得することを目的としています。今後、並列化は当たり前のものとなり、さまざまな形でサポートされるようになります。並列化処理の根底に流れる考え方を身につければ、その変化に対応できます。 今回はインテルTBBのアルゴリズムテンプレートとループの並列化について解説します。この連載のサンプルはあくまでもインテルTBBの使い方を説明するものであり、実務を特別に意識したものではありません。その点をご理解下さい。 対象読者 筆者が想定している読者はC++の基本的文法を理解し、並列化プログラミングに興味を持っている方です。高度なC++テクニックを極力さけ、基本的な文法さえ分かれば読めるように極力注意しますので、並列化に興味を持っている方はぜひこの連載に目を通して下さい。 必要な環境 C++コンパイラが必要です。お持ち
-
約30ドルの超小型コンピュータ「Raspberry Pi」でスパコンを自作しよう - ZDNet Japan - Linkis.com
自作（DIY）コンピュータと言えば、おそらく多くの人が、超高性能のゲーム用コンピュータを組むことや、安価な部品を組み合わせて最低限の費用でPCを作ることをイメージするだろう。スーパーコンピュータを作ることなど、想像しないはずだ。しかし、考えてみるべきかもしれない。米ボイジー州立大学、電気・計算機工学科の博士課程の学生であるJoshua Kiepert氏は、「Raspberry Pi」（RPi）コンピュータを使って、2000ドル以下でミニスーパーコンピュータを作り出した。 RPiは、シングルボードのLinuxコンピュータだ。RPiはCPUに700MHzの「ARM11」プロセッサ、GPUに「VideoCore IV」を搭載している。Kiepert氏が使ったモデルBは、512 MバイトのRAMを持ち、2つのUSBポートと10/100 BaseTイーサネットポートが付いている。Kiepert氏はそ
-
アクターモデル - Wikipedia
アクターモデル（英: actor model）とは、1973年、カール・ヒューイット、Peter Bishop、Richard Steiger が発表した並行計算の数学的モデルの一種[1]。アクターモデルでは、並行デジタル計算の汎用的基本要素として「アクター」という概念を導入している。アクターモデルは並行性の理論的理解のフレームワークとして使われるほか、並行システムの実装の理論的基礎としても利用されてきた。 アクターモデルはそれ以前の計算モデルとは異なり、物理法則を発想の基本としている。他にも、LISP言語、Simula言語、ケーパビリティ・システム、パケット通信、初期のSmalltalkなどの影響を受けている。アクターモデルは「数百・数千のマイクロプロセッサから構成され、個々にローカルメモリを持ち、高性能通信ネットワークで通信を行う並列コンピュータが近い将来登場するとの予測」から開発され
-
並列コンピューティング - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "並列計算" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年10月) 並列計算（へいれつけいさん、英語: parallel computing）は、コンピュータにおいて特定の処理をいくつかの独立した小さな処理に細分化し、複数の処理装置（プロセッサ）上でそれぞれの処理を同時に実行させることである[1]。並列コンピューティングや並列処理ともいう。 大きな問題を解いたり、大量のデータを処理したりする過程は、より小さなサブタスクやサブデータグループの処理に分割できることが多い、という事実を利用して単位時間あたりの処理効率（スループット
-
グスタフソンの法則 - Wikipedia
グスタフソンの法則（英: Gustafson's law、Gustafson-Barsis' law としても知られる）は、計算機工学における法則で、「十分に大きな規模の問題は、効率的に並列化して解くことができる」事を示すものである。グスタフソンの法則は、並列化によってプログラムが高速化できる限界を示したアムダールの法則と密接に関係している。本法則は、ジョン・グスタフソンによって1988年に初めて示された。 P がプロセッサの数であり、S がSpeedup、α がプロセスの並列化できない部分であるとすると、下記が成立する。 グスタフソンの法則は、計算機の規模が大きくなると利用可能な計算能力を使い切るほど性能がスケールしないというアムダールの法則に欠けていた部分に対応するものである。グスタフソンの法則では、問題の規模が固定である、また並列プロセッサ上の計算の負荷が一定であるという仮定を取り除
-
GNU Parallelがすごすぎて生きるのがつらい
皆さん今日もたくさんのサーバを相手にされていることかと思いますが、いくつかのサーバにアクセスして 1 秒間の統計情報(例えばvmstat 1 2)を集めてパッと表示したい時ってどうやってますかね？shell script を学びはじめたばっかりの僕はこんな感じで書いてました。 $ for i in host1 host2 host3; do ssh $i "vmstat 1 2 | tail -1"; done 0 0 0 329004 210836 14275360 0 0 0 2424 1410 1828 0 0 100 0 0 0 0 0 3716112 587704 25921684 0 0 0 488 1643 2026 0 0 100 0 0 1 0 0 555440 265560 14015548 0 0 0 4204 1534 2392 1 0 99 0 0 vmstatと
-
-
マルチコア時代に備えて本気でメモリモデルを理解しておこう - リオーダー & finalフィールド 編 - - かとじゅんの技術日誌
長い文章になってしまったので、概要だけ先に書きます。 以下のJavaプログラムは、常に上から下に順番に命令が実行されると思いますか？つまり、aに1が格納された後に、bに2が格納されると思いますか？ 実は場合によってはこの実行順序が入れ替わる場合があります。これはJavaの言語仕様として定義されていることです。これを考慮しないと信頼性のある並行処理は実装できません。 気になる人は以下を読んでみてください。 a = 1; b = 2; すでにインターネットは社会インフラ化しています。ソーシャルネットワークで多くの人とコミュケーションやコラボレーションできる時代で、個人が情報を作り消費することは当たり前になってきています。そして、インターネット上のコンテンツは増加の一途を辿っています。「情報爆発」なんて言葉も耳慣れた言葉になりましたが、その問題解決のためにMapReduceなどの分散処理技術に注
-
アムダールの法則 - Wikipedia
複数のプロセッサを使って並列計算してプログラムの高速化を図る場合、そのプログラムの逐次的部分は、制限を受ける。例えば、仮にプログラムの95%を並列化できたとしても、残りの部分である5%は並列処理ができないため、どれだけプロセッサ数を増やしたとしても、図で示したように20倍以上には高速化しない。 アムダールの法則（アムダールのほうそく、英語: Amdahl's law）は、ある計算機システムとその対象とする計算についてのモデルにおいて、その計算機の並列度を上げた場合に、並列化できない部分の存在、特にその割合が「ボトルネック」となることを示した法則である。コンピュータ・アーキテクトのジーン・アムダールが主張したものであり、アムダールの主張（アムダールのしゅちょう、英語: Amdahl's argument）という呼称もある[1]。 複数のプロセッサを使い並列計算によってプログラムの高速化を図る
-
1
公式Twitter
- @HatenaBookmark
リリース、障害情報などのサービスのお知らせ
- @hatebu
最新の人気エントリーの配信
キーボードショートカット一覧
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Copyright © 2005-2024 Hatena. All Rights Reserved.
設定を変更しました