Schedulable lightweight virtual processes and concurrent loops P&L: -11.5 (≃ -15638 JPY)
Imagine a nested for loop, it is composed of multiple loops. We can simulate concurrency by executing parts of loops and rapidly switch between them.
This is what a kernel scheduler does and I think it's a very interesting part of an operating system. Unfortunately most programs are not written to be multithreaded so computers use very little of resources available to them.
真のマルチスレッドを使用できるように、PythonコードをJavaで書き直します そのスレッド番号に一致するN番目の製品を繰り返し実行しようとするループランナースレッドを実装します
Rewrite Python code in Java so true multithreading can be used Implement loop runner threads that repeatedly try execute Nth product that matches that thread number
2時間 私は自分が作成したものにかなり満足しています。 APIの方がいいと思います。または、結果を待つ実装の方が良い場合があります。 ネストされたループがあるため、新しい結果があるかどうかを確認するための計算にはコストがかかります。これはもっとうまくできると思います。 理想的には、ネストされたループは、いくつかのdivmod命令と追加のみを必要とします。それ以外の場合は、使用されるパフォーマンスを支配します。
2 hours I am fairly happy with what I created. I think the API could be better. Or the implementation of waiting for results could be better. The calculation to see if there are any new results is expensive due to nested loops. I think this could be done better. Ideally nested loops should only take a few divmod instructions and additions. Otherwise they shall dominate performance used.
2〜4時間いつ始めたのか思い出せない
エントリが重複しています。
親ループは次のようになります。
文字の文字の場合: 数の数の場合:
シンボル内のシンボルの場合:
次に、innerloop内の新しい並行ループで拡張してみます。
しかし、各反復は同じように見えます!これと同等ではありません:
文字の文字の場合: 数の数の場合:
シンボル内のシンボルの場合:
ネストされたコードの場合: ネストされた絵文字の場合: print(文字番号記号ネストされた絵文字)
ループのツリーのように、ループを任意の数のループに拡張する方法が必要です。
2-4 hours I cannot remember when I began
I get duplicate entries.
The parent loop looks this:
for letter in letters: for number in numbers: for symbol in symbols:
Then I try extend it with a new concurrent loop inside the innerloop.
But each iteration would look the same! It's not equivalent to this:
for letter in letters: for number in numbers: for symbol in symbols: for nested in codes: for emoji in nested: print(letter + number + symbol + nested + emoji)
I need some way of extending the loop through an arbitrary number of loops, like a tree of loops.
私はこれに1時間を費やしました。私は本当に開発の気分ではありませんでしたが、突き進みました。
I spent 1 hour on this. I wasn't really in the mood for development but pushed through.
私は自分の論理のバグに気づきました。 スレッド0は、ループの反復0〜8を担当します スレッド1は8-16を担当します スレッド2は16-24を担当します 等々 ラップアラウンドを処理しないという数学的ロジックが原因で、現在、間違ったスレッドでループの反復を実行しています。モジュロ演算子を使用します。 理想的には、各ティッカーはその範囲のスレッドでのみ呼び出されます。
I realised my bug in my logic. Thread 0 is responsible for loop iterations 0-8 Thread 1 is responsible for 8-16 Thread 2 is responsible for 16-24 And so on I'm currently executing loop iterations on the wrong thread due to a mathematical logic of not handling wraparound. I use the modulo operator. Ideally each ticker is only called on the thread for its range.
解決する必要のある問題があります。これは並列処理とは関係ありません。
このようなネストされたループがあると想像してください
`
手紙の場合手紙の場合:数の数について:
印刷(文字番号)
シンボル内のシンボルの場合:
印刷(文字記号)
`
これらの3つのループを同時に実行したいと思います。 1つのアプローチは、インデックスに基づいて実行する関数を選択することです。そして、数字と文字をラウンドロビンで結合します。 だから私たちは
A1
A÷
A2
A×
このアプローチの問題は、ループが分離されていないことです。それらはマージされた1つのループです。
コレクションをマルチコレクションにすることでこれを解決できると思います。 [文字、[数字、記号] そして、各サブリストのラウンドロビンから選択し、ループを個別のオブジェクトとして公開します。
I have a problem I need to solve. Which isn't related to the parallellism.
Imagine I have a nested loop that looks like this
``` For letter In letters:
For number in numbers:
Print(letter + number)
For symbol in symbols:
Print(letter + symbol) ```
I want these three loops to run concurrently. One approach is to pick the function to run based on the indexes! And merge the numbers and letters together round robin. So we get
A1
A÷
A2
A×
The problem with this approach is that the loops aren't separate. They're one loop that has been merged.
I think I can solve this by causing collections to be a multi collection. [Letters, [numbers, symbols] And picking from each sublist round robin and exposing the loops as separate objects.
私はこれのマルチスレッドバージョンをJoinableループなしで作成しました。でも今回は休憩中です。 どういうわけか、マルチスレッドを結合可能なループに結び付ける必要があります。 参加可能ループが2つ以上の値を受け取った場合、処理を続行します。これにより、パイプライン処理での分割とマージが可能になります。 結合されたプロセスをできるだけ早く発生させ、マルチスレッド化する必要があります。 私の設計では(まだJavaで実装していません)、各スレッドには、チェックできるものを再チェックしてチェックするスケジューラがあります。 問題は、ティックをスレッドに分割することです。ティッカーのレベルが1つしかない場合は簡単です。 一度に8つのバッチにチェックマークを付けることができます。別のスレッドで。 私の例では、3つのコレクションのネストされたループと、2つのタスクに分割され、それらの2つのタスクが1つのタスクに結合されて、結果が出力されます。 ネストされたループ、個別のタスク、および結合されたタスクをバッチで実行する必要があります。 古いスレッドに同時ループを送信する方法が必要です。すべてのスレッドによってチェックされるティックプールと呼ばれる共有コレクションを持つことができます。 現在の製品番号はスレッドに関連付けられています。 64は8の倍数であるため、÷8を選択しました。スレッドあたりのバッチ数をクリーンアップします。
`
一方(真){
ティックプールのForループ:
current [loop] <thisThreadN [loop]の場合:
current [loop] = current [loop] 1
NewTickersOrResult = Loop.tick()
NewTickersOrResult.isTickersの場合:
そうしないと:
}
`
I created a multithreading version of this without the Joinable loops. But at this time I am taking a break. I need to somehow tie the multithreading to the joinable loop. When Joinable loop received 2 or more values, it continues processing. This allows a split and merge in pipeline processing. I want joined processes to occur as soon as they can and to be multithreaded. In my design - that I am yet to implement in Java - each thread has a scheduler that rechecks what can be ticked and ticks it. The problem is splitting ticks over threads, it's easy if there is only one level of tickers. You can just tick batches of 8 at a time. In separate threads. My example has a nested loop of 3 collections and a split into two tasks and then those two tasks join into one task to print out the results. I want the nested loops, separate tasks and the joined tasks to be executed in batches. Kind of need a way to send concurrent loops to old threads. Could have a shared collection called the tick pool which is checked by all threads. The current product number is associated with a thread. I picked ÷ 8 due to the 64 being a multiple of 8. Clean number of batches per thread.
```
While (true) {
For loop in tick pool:
If current[loop] < thisThreadN[loop]:
current[loop] = current[loop] + 1
NewTickersOrResult = Loop.tick()
If NewTickersOrResult.isTickers:
Else:
}
```
複数のCPUコアのパフォーマンスをどのように利用するかを考えています。コードの書き方を大幅に見直す必要があります。
ループは私の設計と簡単に並列化できることに気づきました。
N = 0 .. N=3×3×3
Nごとにすべてのスレッドでtickメソッドを実行すると、ループ全体を一度に実行できます。
I am thinking of how to use the performance of multiple CPU cores. It requires a drastic rethinking of how we write code!
It occurred to me that loops could be trivially parallelized with my design.
N = 0 .. N = 3×3×3
If you ran the tick method on all threads with every N, you could run the entire loop in one go.
複数のティッカーからの入力を待ってから出力を送信する結合可能なティッカーを作成する必要があります。 これにより、分割してマージするパイプラインを作成できます。
I need to write a Joinable Ticker that waits for inputs from multiple tickers before sending output along. This lets us create pipelines that split and merge.
スレッドごとに必要なwhile(true)ループは1つだけであることを付け加えておきます。 他のすべては、スレッド内で同時にスケジュールできます。
I shall add that you only need one while (true) loop per thread. Everything else can be concurrently scheduled within a thread.
それが私がそれを仮想並行性と呼ぶ理由です。 IOの同時実行性を提供するには、スレッドを使用する必要があります 永久にループしたり、ブロックしたりするものは作成できません。だから私はこれからすべてのコードを書いて、決してブロックしたり、繰り返したりしないようにします。これは、マルチスレッドスケジューラの開発中に学んだ重要な教訓です。
ブロッキングはプログラムからは見えません。プログラムは、ブロックしていることを認識していません。メソッドがブロックして回避できることを知っておく必要があります。 私の他のアイデアは、並列のwhile doループで、構文糖衣構文を介してブロッキングを非ブロッキングに変更します。 こんな感じ
A1=並列while{ Buf = socket.recv(1024) } 行う { Parallel for(Socket socket:sockets){ Socket.send(buf) } } クロスマージA1
この構文は、データの受信をブロックするために複数のスレッドを起動します。そして、それぞれについて、スレッドプール内のスレッドをスピンアップして処理し、すべての接続に並列に送信します。
私が持っているもう1つのアイデアは、優先実行順序を変更することです。そのコードラウンドのそのスケジューラーは、毎回同じ順序でティッカーをロビンします。ループを他のループよりも多く実行できない理由はありません。
That's why I call it virtual concurrency. You would need to use threads to provide IO concurrency Anything that loops forever or blocks cannot be composed. So I shall write all my code going forward to try never block and be reetrant. This is an important lesson I learned while developing my multithreaded scheduler.
Blocking is invisible to the program. The program isn't aware it is blocking. You need to know that a method can block to work around it. My other idea is a parallel while do loop which changes blocking to be non blocking through syntactic sugar. It looks like this
A1 = parallel while { Buf = socket.recv(1024) } Do { Parallel for (Socket socket : sockets) { Socket.send(buf) } } Crossmerge A1
This syntax spins up multiple threads to block on receiving data. And for each one it spins up a thread in a thread pool to handle it and send it to every connection in parallel.
Another idea I have is to change the priority execution order. That scheduler in that code round robins the tickers in the same order every time. There's no reason why we cannot execute the loops some more than others.
面白い。 Pythonでの同時実行のネイティブサポートは使用せず、基本的な列挙、インデックス作成、割り当てのみを使用しました。それが理解するのに必要なことだと思います。これには教育的価値があります。
Interesting. You did not use any native support for concurrency in Python, and used only basic enumeration, indexing, assignment. I guess, that is what it takes to understand. This has educational value.