(toppers-users 3758) Re: SSPの制約タスクの待ちについて

[Hiroaki TAKADA]

杉本さん

> こいさんさんが示されたタスク優先度16向けのコードには入っていましたが、
> もしかしてそちらを見られているでしょうか？

そちらを見ていました。見る方が間違っていたようで申し訳ありません。

高田広章
名古屋大学

(12/01/18 8:13), 杉本明加 wrote:
> 高田先生
> 
> 杉本です。
> 
> 今のコードですが、ループは入っていません。
> 最新のパッケージで確認しました。
> 
> Inline uint_t
> bitmap_search(uint_t bitmap)
> {
> 	uint_t	n = 0U;
> 
> 	if ((bitmap&  0x0fU) == 0U) {
> 		bitmap>>= 4U;
> 		n += 4U;
> 	}
> 	return (n + bitmap_search_table[(bitmap&  0x0fU) - 1U]);
> }
> 
> となっています。
> 
> ループのある個所ってどこでしょうか？
> こいさんさんが示されたタスク優先度16向けのコードには入っていましたが、
> もしかしてそちらを見られているでしょうか？
> 
> ちなみにタスク優先度16向け対応の修正では、ASPと同じようにもう1つ条件文を
> 追加しています。
> 
> 
> 以上、よろしくお願いします。
> 
> 
> 
> 2012年1月18日0:48 Hiroaki TAKADA<hiro ＠ ertl.jp>:
>> 杉本さん
>>
>>> コードはいっしょになっていないとは思いますが、流れはいっしょという
>>> 意味でアルゴリズムが同じと書きました。認識違ってますでしょうか？
>>
>> ASPカーネルのコードはループがないが、SSPカーネルのコードはループが
>> あるという意味では、違うアルゴリズムであると思います。アルゴリズムの
>> 性能としては、O(n)とO(log n)という違いがあります（nは優先度の段数）。
>>
>>> ただ、実はbitmap_search以外でも細部でASPと異なる個所が複数SSPの実装に
>>> 存在しています。というのはMISRA-Cチェッカで検出される違反部分を
>>> コードの挙動を変えない範囲で変更しているためです。
>>
>> 理由があって、ASPカーネルと違うコードになっているのであれば、ASPカー
>> ネルと合わせる必要はないと考えます。
>>
>> ですので、bitmap_searchについては、
>>
>>>>> bitmap_searchはASPとアルゴリズムを共通にしたいため
>>
>> という認識であればコードも同じにすれば良いと思いましたが、理由があっ
>> てアルゴリズムを変えたのであれば、ASPカーネルに合わせる必要はないです。
>>
>> 高田広章
>> 名古屋大学
>>
>> (12/01/18 0:08), 杉本明加 wrote:
>>> 高田先生
>>>
>>> 杉本です。
>>>
>>>> 現状、ASPカーネルのアルゴリズムとは違っていますよね？ 16段階にする際に、
>>>> 全く同じにしてしまってはどうでしょうか？
>>>
>>> コードはいっしょになっていないとは思いますが、流れはいっしょという
>>> 意味でアルゴリズムが同じと書きました。認識違ってますでしょうか？
>>> ASPと実装を揃えること自体は特に問題ありません。
>>>
>>>
>>> ただ、実はbitmap_search以外でも細部でASPと異なる個所が複数SSPの実装に
>>> 存在しています。というのはMISRA-Cチェッカで検出される違反部分を
>>> コードの挙動を変えない範囲で変更しているためです。
>>> # 逸脱手続きさえ踏めば問題ない作りになっていると思いつつ、異常な数の
>>> # 違反を見てしまうと、逸脱手続きを踏むよりはコードを直した方がいいだろうなぁと思ってしまいます。
>>>
>>> bitmap_searchの実装を揃えるならば、他の修正もいったん元に
>>> 戻そうかと思います。
>>>
>>>
>>> 以上、よろしくお願いします。
>>>
>>>
>>> 2012年1月17日23:11 Hiroaki TAKADA<hiro ＠ ertl.jp>:
>>>> 杉本さん
>>>>
>>>>> bitmap_searchはASPとアルゴリズムを共通にしたいため
>>>>> 現在の実装となっています。また、ソースコードの可読性も
>>>>
>>>> 現状、ASPカーネルのアルゴリズムとは違っていますよね？ 16段階にする際に、
>>>> 全く同じにしてしまってはどうでしょうか？
>>>>
>>>> 高田広章
>>>> 名古屋大学
>>>>
>>>> (12/01/17 16:58), 杉本明加 wrote:
>>>>> 宮川さん、こいさんさん
>>>>>
>>>>> 杉本です。
>>>>>
>>>>> 宮川さんにご紹介いただいたやり方ですが、どこかの書籍で
>>>>> 読んだ記憶があり、その時はよく考えるなぁと思ったものでした。
>>>>>
>>>>>
>>>>> bitmap_searchはASPとアルゴリズムを共通にしたいため
>>>>> 現在の実装となっています。また、ソースコードの可読性も
>>>>> 考えると現状のコードのままにしたいと考えています。
>>>>> （タスク優先度16の場合については次期リリースに含みます）
>>>>>
>>>>> ただ一方で、メモリ使用量が減らせる実装は取り入れたいと
>>>>> 思う部分があり、他の実装を取り入れることでROMが減りそうで
>>>>> あれば他の実装コードを参考としてパッケージに含めるのはありとも思っています。
>>>>>
>>>>> 以上、よろしくお願いします。
>>>>>
>>>>>
>>>>> 2012年1月17日11:10 Miyagawa<miyagawa ＠ sanritz.co.jp>:
>>>>>> 宮川です。
>>>>>>
>>>>>> 余計な突っ込みかも知れませんが、、、
>>>>>>
>>>>>>> Inline uint_t
>>>>>>> bitmap_search(uint_t bitmap)
>>>>>>> {
>>>>>>>     uint_t n;
>>>>>>>     for(n = 0U; n<    3; n++){
>>>>>>>      if ((bitmap&    0x0fU) == 0U) {
>>>>>>>       bitmap>>= 4U;
>>>>>>>      }else{
>>>>>>>       break;
>>>>>>>      }
>>>>>>>     }
>>>>>>>     return (n*4U + bitmap_search_table[(bitmap&    0x0fU) - 1U]);
>>>>>>> }
>>>>>>
>>>>>> n<= 3 ? は置いといて、
>>>>>>
>>>>>> 良く知られた方法としては、こんな手もあります。(16bit)
>>>>>>
>>>>>>     x = (x&    (-x)) - 1
>>>>>>     x = (x&    0x5555) + ( (x>>    1)&    0x5555)
>>>>>>     x = (x&    0x3333) + ( (x>>    2)&    0x3333)
>>>>>>     x = (x&    0xffff) + ( (x>>    4)&    0xffff)
>>>>>>     x = (x&    0x00ff) + ( (x>>    8)&    0x00ff)
>>>>>>
>>>>>> 固定時間だし、シフトと足し算だけなのでそれなりに速いと思います。
>>>>>>
>>>>>> --------------
>>>>>>