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

[Hiroaki TAKADA]

杉本さん

> コードはいっしょになっていないとは思いますが、流れはいっしょという
> 意味でアルゴリズムが同じと書きました。認識違ってますでしょうか？

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)
>>>>
>>>> 固定時間だし、シフトと足し算だけなのでそれなりに速いと思います。
>>>>
>>>> --------------
>>>>