ピクセル・コビー 図 9 タイルの貴し 実行前 実行後 33 22 11 DD CC 1 1 BB 00 AA BB AA 境界の揃ったメモリ・ワード 読込み元ポインタ 境界の揃ったメモリ・ワード 書込み先ポインタ 境界の揃ったメモリ・ワード 右端においては、サーバーはスパンの終り以降のすべ てのステイプル・ピットをマスクする。ステイプルの データに対するこれらの調整は、すべての透明ステイプ ルのスパンのワードを左端と右端とで効果的に揃える。 ーは 0 の N 。 Op 性を利用して、残りのスティ プル・ビットが 0 である場合に、スパンの 32 ピクセル・ セグメントの描画を止める。 書込み先ピクセルに応じて変化するグラフィックス関 数を使って透明ステイプルを描画する場合、 16 の枝を もつ分岐はステイプル・パターンがまばらな ( 1 のピ ットが少ない ) ものでないとうまく働かない 23 。咼速の write 命令ではなく、低速の読込み / 変更 / 書込みシーケ ンスになってしまうためである。さいわい、一般化さ れたグラフィックス関数はこの状況にうまく適合する。 ーは、不透明ステイプルのために作成されたも のに似た 16 工ントリのテープルを使用するが、スティ プルが 0 の部分は背景ピクセルを描画するのではなく、 NoOp(andbits がすべて 1 、 xorbits がすべて 0 ) にな るようにする。結果のコードは不透明ステイプルのコー ドによく似ているが、アラインメントとループの終了を 実現するために 0 のビットがもつ N 。 Op 特性を使用し ている。 タイル タイル塗潰しは、ピクセルをタイルから書込み先にコ ピーする。読込み元と書込み先のアラインメントは、相 互にどのようになっていてもよい。図 9 は、タイル塗潰 しの最初の 2 ピクセルである。 23 訳注 : 1 のピットが少ない、つまり 0 が多いということは、プレーン マスクカ陏効で、書込みのみで描画できることを意味する。 88 こでも、サーバーは、スパンの内部を一度に 4 ピ UNIX MAGAZINE 1991.10 性能を表す数値はすべて、 xllperf プログラムによっ 書き換える方法を示す。 ズムを単純な数学的変換によって、より効率的な形式に いかたちに記述されてしまう理由と、これらのアルゴリ 節では、よく知られたアルゴリズムがしばしば最適でな のピクセル・コピーの手法を示す。最後に線分の描画の Area では、読込み元がキャッシュ・メモリ内にない場合 テイプルとして描画する場合の変更方法を示す。 Copy- 狭く縄区しのないピットマップを、透明および不透明ス を説明する。 PolyText と ImageText の例では、幅が まざまな塗潰しスタイルの手法をどのように変更したか る。 こでは、特定の描画操作に適合させるために、さ X プロトコルには、何種類かの描画リクエストがあ 描画リクエストの高速化 たのちに、塗潰し関数を使用する。 する andbits と xorbits に格納する前処理をおこなっ で、サーバーはピクセル・データの 32 ビットを、対応 化された Copy 関数は塗潰し関数よりもさらに複雑なの ーはタイルのビット群を適当に回転させる。一般 トーンの実現に使用する。ステイプルの場合と同様に 幅 4 ピクセル高さ 6 ピクセルのタイルをカラー・ハーフ る。たとえば、 Display PostScript System[1][7] は、 分である。各ピクセルに任意の色を使用できるからであ れは 4 ピクセル幅にすぎないが、たいていはこれで十 ーは幅が 32 ビットのタイルを最適化する。 CopyArea の手法を使用する。 することはできないので、サーバーでは彳する低速の 残念なことに、 C 言語からこれらの命令に直接アクセス レスか揃っている場合にくらべて 1 サイクル多くなる。 シュされている ) にストアされるので、この処理はアド ードを読み取る。タイルはつねにメインメモリ ( キャッ 令と Load Word Right 命令を使って、タイルの各ワ ーは Load Word Left 命 できる。理想的には、サーバ セットでは、アドレスか揃っていない場合も容易に処理 トが同しである ) 場合には容易である。 MIPS の命令 ている ( 読込み元と書込み先のアドレスの最下位 2 ピッ クセルすっ塗り潰す。これは読込み元と書込み先か揃っ

はもっとも高速な手法である。レジスタ・アロケータに 悪影響を与えすに、 swl 命令と swr 命令を直接使うこと はまず不可能である。 グラフィックス関数の最適化 X における画像の生成は、 3 つの独立した間題に分 割できる。描画するイメージの形状の計算、描画すべき ピクセルの計算、そして、新たに描画するピクセルと既 存の書込み先ピクセルとの結合 ( 演算 ) である。概念的 には、イメージの形状は、、スパン " のリストに分割され る。スパンとは、スキャンライン上の連続するピクセ ルの並びである。各スパンは指定された塗潰しスタイル (fill style) に従って、読込み元ピクセルの ( かならすし も連続していない ) 並びに変換される。これらの読込み 元ピクセルは、指定されたグラフィックス関数 ( ラスタ・ オペレーション ) に従って書込み先ピクセルと結合され る。実際には多くのアルゴリズムは各スパンを即座に塗 り潰す。また、対象となるすべてのスパンに共通する情 報をあらかじめ計算しておく。本節では、グラフィック ス関数をどのように処理するかを述べる。このあとの 2 つの節では、さまざまな塗潰しスタイルを効率よく描画 する方法と、通常の X 描画リクエストに固有の問題を どのように扱うかを述べる。 X プロトコルでは、 16 種類の 2 項論理関数を使用し て、 1 つの描画するピクセルと 1 つの書込み先ピクセル とが結合できる。ピクセルが複数のビットて構成される 場合、同しグラフィックス関数がすべてのビット ( ある いはプレーン ) に適用される。表 1 に、各グラフィック ス関数の名前と定義を示す。 プロトコルはプレーンマスクもサポートしている。プ レーンマスクが 1 のピットをもっているところでは、グ ラフィックス関数の結果は対応する書込み先ビットにか ならす書き込まれる。プレーンマスクが 0 のピットをも っところでは、対応する書込み先ビットはそのままで変 更されない。 FUNC が上記の 16 の論理関数の 1 つで あるとすると、プレーンマスク・セマンティクスは次の ように表せる。 ((src FUNC dst) AND planemask) OR (dst AND (NOT planemask) ) 80 表 1 X11 のグラフィックス関数 関数 Clear And AndReverse Copy AndInverted NoOp Xor Or Nor Equiv lnvert (_)r Reverse CopyInverted OrInverted Nand Set 定義 0 src AND dst src AND (NOT dst) src (NOT src) AND dst dst src XOR dst src OR dst NOT (src OR dst) NOT (src XOR dst) NOT dst src OR (NOT dst) NOT src (NOT src) OR dst NOT (src AND dst) 1 プレーンマスクのヒ、ツトが全部 1 の場合には、 単純な次の式に置き換えられる 7 src FUNC dst もっと DECstation 3100 のフレームノヾッフアにはハードウ ェア・プレーンマスクがあるが、 DECstation 5000 / 200 のフレームバッフアにはない。また、どちらのフレーム バッフアにも前掲の 16 のグラフィックス関数を実現す るハードウェアはない。そして、オフスクリーン・イメー ジ ( ピックスマップ ) が存在するメインメモリにも、グ ラフィックス関数やプレーンマスクのための専用の論理 回路はない。したがって、効率のよい X11 のグラフィッ クス関数と、プレーンマスクの効率のよいソフトウェア を実装する必要があった。 単純に考えれは・、 32 個のグラフィックス描画ルーチン を実装すればよい。つまり、 16 のグラフィックス関数の それぞれについて、完全なプレーンマスク・セマンティ クスをもつものと、プレーンマスクがすべて 1 の単純な セマンティクスをもつものを実装するわけである。この プログラムは多量のメモリを消費する。 もう 1 つの手法は、動的なコード生成である。この場 合、描画プログラムは実行時に生成される。この手法は 単純なグラフィックス・システムではうまくいくが、 XI 1 7 訳注 : プレーンマスクが 0 なら、 dst " になる。 UNIX MAGAZINE 1991.10

図 6 透明ステイプルの貴しスタイル 図 8 書込み命令だけを使用する透明スティカレ 必要な書込み数書き込まれるバイト書込み命令 書込み先ポインタ 境界の揃ったメモリ・ワード DD CC BB AA 0 実行前 ・ロロロコロロ 0 コ 0 ロ 0 コ 0 ロ 0 コ ロロロこロ 0 ロ : 00 ロこ 00 コ一一 ロロ 00 ロロロ〔 0000 ココ - = 一 ロロロ 00000 ロロロロ〔 UUU ()o writes) sb fg, sh fg, O(pdst) sb fg, 2(Xist) sb fg, 0 ( 8S0 : sb fg, 2(xist) sb fg, sb fg, 2(pdst) swlfg, 2(xist) sb fg, sb fg, 0(pdst); sb fg, 3(pdst) sb fg, 1 ( 〆 s sb fg, sh fg, 0 ( 既 sb fg, 3(pst) sh fg, 2(Xist) sb fg, 0(pdst); sh fg, 2(xjst) swr fg, l(pdst) sw fg, 0(pdst) 0 1 ステイプル・ビット . 1 0 1 1 1 透明ステイプル 境界の揃ったメモリ・ワード fg CC fg AA 図 7 読込み / 変更 / 書込みによる透明スティカレの実装 グリフ・ビット . 1 0 0 1 ィー ( 4 04 -1 実行後 1 2 2 ( 4 1 2 1 前景 書込み先 ロロ 0 ロ 00 FF FF 00 ロ■ 0 ロのロロの 1 / ☆ Get 4 bits of stipple ☆ / / ☆ Ge し mask / ☆ Mask destina し ion / ☆ Mask foreground / ☆ Merge し he し WO / ☆ Next 4 s し ipple bits i ndex srcbits & 0xf; mask mask し able[ index] ー dst *pdst & mask; f oreground & —mask ー src ☆ pdS し ds し一 src; srcbits = srcbits > > 4 な上書きではなく、書込み先ピクセルによって結果が変 わるグラフィックス関数を扱わなければならない。サー ーは書込み先ピクセルを単純に 0 にしたり前景ピクセ ルをマージすることはできない。たとえは、 Xor は書込 透明ステイプルはピットマップをピクセルにマップす み先をマスクしてはならないが、 lnvert は適切な書込み る。ビットマップ中の 0 のビットについては、サー 先ビットを反転し、前景を完全に無視しなければならな は対応する書込み先ピクセルに変更を加えない。ビット い。その代わり、書込み先ピクセルに上書きする 4 つの マップ中の 1 のヒ、ツトについては、サーバーは前景ピク グラフィックス関数は読込みを完全に避けることができ セルを対応する書込み先ピクセルにマージする。図 6 に る。ストア命令をうまく使うことにより、図 8 に示すよ 透明ステイプル塗潰しの最初の 3 ピクセルを示す。 うに、サーバーはワードのはとんどの連続する 1 ~ 4 バ こでも、スパンのなかはどのワードを描画する方法 イトを 1 メモリ・サイクルで書き込める ()g レジスタは に焦点を絞る。従来の透明ステイプルの実装では、書込 4 バイト全部に前景ピクセルを含んでいる ) 。 み先ワードを読み取り、上書きされるピクセルをマスク し、新しいピクセルをマージし、最後に変更されたワー 4 ビットで表される 16 のパターンでは、全部で 21 の ドをメモリに書き戻す。図 7 にこのプロセスを図示し、 書込み命令がある。それぞれの場合が等しい頻度で現れ これを実装するための C のコードも併せて示す。 るとすると、各 4 ビットごとに平均して 21 / 16 回の書 込み命令が必要である。これは、 DECstation3100 で この手法でおもに間題となるのはその性能である。 DECstation 3100 では、最良のコードでも各 4 スティ は 8.75 サイクル、 DECstation 5000 / 200 では 5.9 サ プル・ピットごとに 16 サイクル近くもかかってしまう。 イクルに相当する ( ページモード書込みの場合 ) 。ほと この数値は DECstation 5000 では、読込み時間がよけ んどのステイプルにはランダムな場合よりも多くの連続 いにかかるのでさらに悪くなる。また、この手法は単純 するビットがあり、描画はワード内の残りのピットがす 透明ステイプル 86 UNIX MAGAZINE 1991.10

X サー ハーの高速化 図 4 ソリッド塗潰し描画コード Pixe18 int Pixe132 *pdst ; width , raggedLeftBytes ; fgandbits, fgxorbits ; / * Paint ragged left edge * / CFBFILLLEFT(pdst , fgandbits , fgxorbits) ; ー = raggedLeftBytes ; width pdst + = raggedLeftBytes ; / * paint full words until 1 ー 4 pixels left * / while (width > 4 ) do { CFBFILL ( ( Pixe132 *)pdst, fgandbits, fgxorbits) ; width pdst + = 4 ; / * Paint ragged right edge * / CFBFILLRIGHT (pdst + width—l , fgandbits , fgxorbits) ; 表 6 不透明スティカレの前景 / 背景マッピング・テーカレ グリフ・ビット 0000 0001 0010 1110 1111 andbits bga bga bga bga bga bga bga fga bga bga fga bga fga fga fga bga fga fga fga fga xorbits bgx bgx bgx bgx bgx bgx bgx f gx bgx bgx fgx bgx fgx fgx fgx bgx fgx fgx fgx fgx 表 6 に示すように fgandbits 、 fgxorbits 、 bgandbits 、 UNIX MAGAZINE 1991.10 塗り潰すときには、サーバーがもっている専用描画ルー アプリケーションが矩形などの図形をステイプルで だけをフェッチすることに注意 ) 。 うなグラフィックス関数は、 andbits を使わす xorbits トをフェッチするような命令は含まない ( DFC 叩 y のよ プのオーバーヘッドを含んでいるが、ステイプル・ヒ、ツ 令にまで描画時間を減らすことができる。これにはルー ラフィックス関数による描画は、 4 ピクセルにつき 5.5 命 をおこなうループに展開する。これにより、 DFCopy7 データをもっている場合、同時に 4 ピクセルすつの描画 サーバーが 32 ビット以上の描画すべきスティフル・ する 4 ピクセルに対応する。 工ントリは、適切な背景または前景ビットからなる連続 の bgandbits を表し、はかも同様である。各 32 ビット bgxorbits からなる。 bga は 8 ピット ( ピクセルの深さ ) チンに都合のよい大きさのパターンを使うことがよくあ る。とくに、サーバーは 32 ビット幅のステイプルをき わめて効率よく描画する ( サーバーは 2 、 4 、 8 、または 16 ビット幅のステイプルを複製し、 32 ピットの描画 コードを使うようにする ) 。サーバーがスパンを描画す るとき、スティフル・ピットをスパンの始まりに合わせ るように適当に回転 (rotate) し、 32 ピクセルの全体を 通じてこのステイプル・ピットを再利用する。 このような最適化により、 DECstation 3100 のメモ リ帯域幅は飽和するが、 DECstation 5000 では飽和し ない。スパンが十分に広い場合には、 4 つのピクセルに ついて同時に andbits と xorbits を参照し、このデータ を 32 バイト間隔で描画するほうが速い。 DECstation 5000 では、この 4 ピクセルのグループが 3 回以ーヒ繰り 返されないと、メモリの帯域幅は飽和しない 17 。 不揃いな左端において、サー ーは Store Word Right 命令を使用する。右端では Store Word Left 命 令を使用する前に、レジスタにあるソースデータを最上 位バイトへシフトする。 17 訳注 : 96 ピクセル、つまり 32 ピクセルが 3 つ以上続く場合には、 32 ピクセルごとに同しデータカ俵れることを利用した描画をおこな う ( ーヨ殳に、ステイプルの蝠は 32 ピクセルの約数であることが多い。 そのため、多くの場合、 32 ピクセルごとに同じ値になる ) 。この場 合、 32 ピクセルごとに 4 ピクセルすつまとめて同しデータて描画す る。 85

X サーパーの高速化 表 4 CopyArea と類似の縮約されたグラフィックス関数 X11 関数 C lear And AndReverse Copy AndInverted NoOp Xor Or Nor Equiv lnvert OrReversed Copylnverted OrInverted Nand Set D Cgeneral D Cgeneral D Cgeneral DCcopy D Cgeneral D Cxor D Cxor D Cgeneral D Cgeneral DCxor DCxor D Cgeneral DCgeneral D Cgeneral D Cgeneral D Cgeneral 表 5 4 つの CopyArea 関数の定義 Copy 関数 DCcopy DCcopySPM DCxor DCgeneral 定義 XOR ((src AND andbits2) XOR xorbits2) (dst AND ((src AND andbitsl) XOR xorbitsl)) dst XOR ((src AND andbitsl) XOR xorbitsl)) (dst AND xorbitsl) XOR (src AND andbits2) xorbits2 を計算する。次に、一般化された塗潰し関数で 使用するために fgandbits と fgxorbits を則景ピクセル から導出する。そして同様に、 bgandbits と bgxorbits を背景ピクセルから導出する。これらの値は 4 個になる まで複製して 32 ピット幅 ( ワード蝠 ) に増やし、サー バーがスパンの内部を一度に 4 ピクセル ( 1 ワード ) す つ描画できるようにする。 一般化された塗潰し関数を使用する各ソース・ファイ ルは、 3 通りにコンパイルし、一般化されたコピー関数 を使用する各ソースは 4 通りにコンパイルした。ソース コードは、一般化された塗潰し関数やコピー関数を、つ ねに C 言語のマクロ関数を使って、、呼び出す " 。 Make- file は、実際に導出されたグラフィックス関数のうちの 適当なものに制御を渡す。関数がそのパラメータの一部 分しか使わない場合、使われないパラメータは C プリ プロセッサによって出力されたコードから参照されるこ とはない。したがって、描画ルーチンが DFcopy のよ うな関数のためにコンパイルされた場合には、そのルー UNIX MAGAZINE 1991.10 チンは書込み先ピクセルや andbits を参照しない。 X には、ソリッド、不透明ステイプル、透明スティフ ル、タイルの 4 つの塗潰しスタイルがある。本節ではこ れらの塗潰しスタイルと、これらを効率よく描画する手 法について述べる。どの塗潰しスタイルについても 1 つ のスパンの扱いしか記していないが、実際には形状は任 意の数のスパンからなる。なお、、、マージする " という 語は、、グラフィックス関数を読込み元ピクセルと書込み 先ピクセルに適用し、プレーンマスクを使用して結果を 書込み先ピクセルに書き込む " という意味で使う。 ソリッド塗潰し ソリッド塗潰し (SoIid FiII) スタイルはもっとも単純 である。サーバーは、指定されたグラフィックス関数を 用いて前景ピクセルを書込み先ピクセルにマージする。 塗潰しの最適化 83

線分 X プロトコルは、幅が 1 以上の線分を描画するとき に、どのピクセルが影響を受けるかを厳密に決めてい る。ただし、幅が 0 の線分に関するプロトコルの制約 はいくぶんゆるやかである。この場合、サーバーは線分 をほば 1 ピクセルの幅で描画するが、高速なソフトウェ ア・アルゴリズムや既存のグラフィックス・ハードウェ アを自由に使うことができる。本節では、幅が 0 の線分 の描画についてのみ言及する。 Bresenham の描線アルゴリズム [ 4 ] は、整数演算を 用いてもっとも近いピクセルからの線分の距離を計算す る。そして、 1 回の繰返しごとに 1 つのピクセルを描画 する。 0 から 1 のあいだの傾きをもつ線分では、区し ごとにかならす 1 ピクセル右にステップする。この新し い位置から線分までの垂直距離が 1 / 2 ピクセルよりも 小さい場合には、同しスキャンラインのピクセルに描画 する。 1 / 2 より大きい場合には、 1 ピクセル上にステッ プする。 文献によれば、 Bresenham のコードはソフトウェア による実装には向いていないと指摘されることが多い。 たとえは、参考文献 [ 5 Ⅱ 8 Ⅱ 10 ] では次のようなアルゴリ 同しコードを使い、 5.1MB/s を達成する。 ズムカ齠介されている。 *pdst if (e > 0 ) { pdst e = e pdst + + e2 ; e + e 1 ; 1 ; scan1ineWidth; } else { pdst = pdst 変数 e は、線分からのピクセルの距離を表す。 el に よる補正は、水平方向への移動に加算する距離の増分を り効率的な形式に変換できるようにモジュール化されて ズムをどのように導いたかを説明していると同時に、よ [ 10 ] のものがはかよりも明らかに優れている。アルゴリ 直線と円弧の描画の整数アルゴリズムでは、参考文献 分である。 表す。一方、 e2 は垂直方向への移動に加算する距離の増 92 いる。 たとえば、無条件に el を e に加算することによって、 else 部を完全に除去できるし、これは e2'=e2—e1 で 補償できる。 RISC マシン上では問題ないが、 CISC マ シン上では、 if は条件コードをセットするためのテスト 命令を生成するのが普通である。このテストは新しい e の値がその直前に計算されるなら不要である。 e'=e—el のオフセットをすれは、計算を移動できる。改良された アルゴリズムは次のようになる。 *pdst e ' 十 e1 ・ if (e , > 0 ) { pdst = pdst + 1 ; ーは、このコードを囲むループを 4 つに カラーサー 展開する。 1 よりも小さな傾きをもつ線分であれば各点 の描画に平均 5 十 ( 3 / 4 ) 命令かかり、それよりも傾きが 急な線分の場合には 6 十 ( 3 / 4 ) 命令になる。 線分の描画に関する DECstation 3100 の初期のべ ンチマークでは、最悪のケースで予想した結果の 1 / 5 という性能しか出せないことが判明した。 Translation Lookaside Buffer(TLB) トラップの処理を計測するフ ログラムによって、カーネルが現在 TLB 内にないフ レームノヾッフア・メモリのページにアクセスするたびに 38 ″ s も費やしていることが分かった。 R2000 と R3000 では、 TLB は 4KB のページを 56 ページもっことがで きる。カラー・フレームバッフアの各スキャンラインは IKB なので、 1 ページは 4 スキャンラインに相当する。 画面全体は 216 ページであり、 TLB のサイズのほば 4 倍にあたる。垂直距離が大きな線分は、多くの時間を描 画ではなく TLB フォールトの処理に費やしていた。 カーネルは、大部分の TLB フォールトを 17 命令 pdst = pdst + scan1ineWidth; UNIX MAGAZINE 1991.10 教訓 : 2 十 2 が 4 にならなけれはならない場合もある。な 描画は約 9 倍高速化された。 理が遅くなっていた。この問題が解決されると、線分の より、すべてのフレームノヾッフアの TLB フォールト処 リ・インターフェイスが誤って設定されていた。これに しかし、カーネルでは、フレームバッフアへの仮想メモ で処理することができる。これは 1 よりすこし長い。

図 3 に、ソリッド塗潰しの最初の 3 ピクセルを示す。 ーは 32 ビット ( 1 ワード ) の書込み ( グラフィッ クス関数が必要とする場合には読込みも ) を使用して、 最大のバス帯域幅でスパンの内部を埋める。しかし、ス パンの境界はピクセル単位の境界に揃えられているので あって、ワード単位の境界ではない。このため、サーバ ーはスパンの左右の端を特別に扱わなければならない。 ワード幅に満たない ( ワード境界に揃っていない ) 、、不 揃い " な端になることがある。つまり、スパンの左端で はワードの上位 1 ~ 3 バイトだけ描画することがあり、 逆に右端ではワードの下位 1 ~ 3 バイトだけを描画する ことがある。 どのようなアーキテクチャでも、サーバーはワード境 界に揃っていない左端を次の 2 つの方法のいすれかで 描画できる。サーバーは、書込み先アドレスの下位 2 ビ ットを使ってシフトとマスク演算をおこなうか、 4 つの コードへ分岐するかである。右端でも同じ手法が使える が、描画すべき残りのピクセル数のうち下位 2 ビットだ けを使用することになる。 MIPS アーキテクチャでは、不揃いな端を描画する 際に部分ワード命令 (Load Word Left 、 Load Word Right 、 Store Word Left 、 Store Word Right) が意 外に役立っことか判明した。これらは本来、ワード境界 に揃っていない 32 ピット ( 1 ワード ) データにアクセス するためのものである。 ワード境界に揃っていない左端を描画するために、サ ーは ( 必要があれば ) lwr 命令を使って書込み先を読 み取り、このデータを fgandbits および fgxorbits と結 合し、 swr 命令で結果を書き戻し、それから書込み先ポ インタをインクリメントし、書かれたバイト数だけスパ 図 3 ソリッド塗潰しスタイル ンの幅を表す力ウントをデクリメントする。 lwr 命令と swr 命令は 1 ~ 4 バイトを読み書きするので、サーバー はこのパターンをポインタがすでにワード境界に揃えら れている場合にも使用する ( スパンが短く、 1 つのワー ドのなかに完全に含まれる場合、サーバーはスパンの描 画にバイト・アクセスを使用する ) 。 スパン右端の不揃いなバイトを描画する場合も同様で ある。描画する残りのデータが 1 ~ 4 バイトになると、 サーバーはワード単位の描画ループを終了する。その後 ーは、描画される最後のバイトのアドレスで lwl サー 命令と ( 必要があれば ) swl 命令を使用する。 こでも、 これらの命令は 1 ~ 4 バイトにアクセスするので、サー バーはそれらをスパンの右端で無条件に使用する。 次ページの図 4 は、ソリッド塗潰し描画コードのプロ トタイプである。このプログラムは、スパンがフレーム バッフア内の 2 ワードにまたがっている場合に有効で ある。 不透明スティカレ 不透明ステイプルはビットマップをピクセルにマッフ する。ビットマップ中の 0 のビットについては、背景 ピクセルを対応する書込み先ピクセルにマージする。 1 のヒ、ツトについては前景ピクセルを書込み先にマージす る。図 5 に、不透明ステイプル塗潰しの最初の 3 ピク セルを示す。 ソリッド塗潰しと同しように、サーバーはスパン内 部を一度に 4 ピクセルすっ描画する ( ワード単位のア クセスのはうが高速なため ) 。 16 工ントリの andbits— xorbits の組のテープルを使用し、 32 ビットノヾラメー タの andbits と xorbits にマップする。これらの組は 図 5 不透明スティカレ塗潰しスタイル 実行前 実行後 84 DD CC BB fg fg fg fg SOlid Fill fg fg AA fg AA 書込み先ポインタ 境界の揃ったメモリ・ワード 読込み元レジスタ 境界の揃ったメモリ・ワード 実行前 実行後 DD CC BB AA . 1 0 1 不透明ステイプル fg fg AA 書込み先ポインタ 境界の揃ったメモリ・ワード ステイプル・ビット 境界の揃ったメモリ・ワード UNIX MAGAZINE 1991.10

864 本のスキャンラインだけである。ハードウェア・グ ラフィックス・アクセラレータを装備したシステムでは、 残りの 160KB はフォント情報やピックスマップのオフ スクリーン・キャッシュとしてよく使われる 2 。しかし、 メインメモリより性能が劣り、メモリ管理も複雑になる ため、このメモリは利用しなかった。 メインメモリとピデオメモリは、同し内部バスとタイ ミング論理回路を使う。 CPU は、ワード内の 1 ピクセ ルから 4 ピクセルまでの任意の連続したピクセルの読み 書きを、 1 回のメモリアクセスでおこなうことができる。 メモリアクセス時間の実測値は、書込みが 400nS 、読 ) 一 みが 410nS 、読込みと書込みの連続が 760nS であった。 連続した書込みでの帯域幅は 10. OMB / s であり 3 、連続 したコピーでの帯域幅は 5.3MB/s である。 フレームノヾッフアには、 8 ビットのプレーンマスクが ある。これは、 1 ワード ( 32 ビット ) の全体をカバーす るように 4 回複製して 32 ビット幅にして使われる。プ レーンマスクの、、 1 " のピットは、対応する書込み先ビッ トの上書きを許可するものであり、 0 のビットは、対 応する書込み先ビットの変更を禁止するものである。 れによって、 0 のビットが 1 つ以上あるプレーンマ スクをグラフィックス・リクエストが指定したときでも、 ーは読込み / 変更 / 書込みのサイクル 4 をおこなわ なくてもよい ( ハードウェア・プレーンマスクを使えば、 マスクの設定 / 書込みの 2 つの操作だけでよい ) 。 DECstation 5000 / 200CX のフレームノヾッフア・メ モリの構成は、 DECstation 3100 と同じである。ピデ オメモリは CPU とは密結合されていないので、 TUR- BOchannel の I / O バス経由でアクセスされる。フレー ムバッフアに、、ページモード " 論理回路が含まれている ので、大部分の書込みは高速である。 VRAM のあるべ ージへの最初の書込みは、通常のメモリサイクルを使用 2 訳注 : スキャンライン 1 本分は 1 , 024 x 8 ピット = 1 KB で、 1 , 024- 864 = 160 本ぶんが表示されない。 3 訳注 : 1 回のメモリアクセスで 4 ピクセルか書けるので、 4 バイトの書 込みには 400nS かかる。 1 バイトにつき 100 x 10¯9sec なので、 1 秒あたり 107 バイト = IOMB 書けることになる。 4 訳注 . : フレームバッフアに描画するときには、一ヨ殳に 1 ) 書込み先ピットを読み取って (read) 2 ) こちらの描画要求に従って変更し (modify) 3 ) それを書き戻す (write) という操作をおこなう必要がある。 UNIX MAGAZINE 1991.10 X サーパーの高速化 するので 360nS かかる。以降の同しページへの書込み は、高速ページモード・サイクルを使用するので 180nS である ( 1 つの VRAM ページの長さは、フレームバッ フアの 2 スキャンラインにあたる ) 。連続する書込み時 の帯域幅は 22MB/s である。バスには、 120nS のペー ジモード書込みをおこなう能力もある。しかし、ポード 面積の不足により、実際にはこの速度でのアクセスはサ ポートされていない。 ある VRAM ページへの最初のアクセスにおける読 込み時間は 610nS であり、ページモードでの読込みは 440nS である。読込みが遅い原因の 1 つは、最小読込み サイクルが 160nS という TURBOchanne レヾスの設計 にある。さらに、 1 ワードの読込みよりも、キャッシュ からの複数ワードの読込みに最適化されている R3000 チッフの設計にも起因する。連続したコピー時の帯域幅 は 6.0MB/s であり、 DECstation 3100 よりもわすか によいだけである。 ページモード論理回路がポード上でかなりの面積を占 めているため、プレーンマスクの論理回路を入れること はできなかった。しかし、後述するソフトウェア技術に よって、ハードウェア・プレーンマスクの必要性が少 なくなったため、ページモード・メモリアクセスのハー ドウェアのみの実装でも、ほとんどの局面で生能が向上 した。とはいえ、 DECstation 3100 より DECstation 5000 / 200CX のほうが遅い描画処理もある。 CPU の構成 DECstation 3100 は MIPS Computer System の R2000 プロセッサ [ 6 ] を 60ns ( 16.7MHz ) のクロックで 使用している。この CPU は、一般的な整数演算の場合 VAXII / 780 の 12 ~ 14 倍の速度をもつ。 DECstation 5000 は、 R3000 プロセッサを 40ns(25MHz) のクロッ クで使用している。こちらの CPU は、 VAXII / 780 の 約 20 倍の高速である。 どちらのマシンでも、 CPU はダイレクト・マップの 命令キャッシュを 64KB もっており、さらにライトス ルーでダイレクト・マップのデータキャッシュももって いる。本稿では、直前にアクセスされた小さなコードや データ・テープルがキャッシュされるものと仮定してい 77

X サーバーの問速化 タム・カラー・フレームバッフアの場合 by Joel McCormack プロセッサの処理速度は、メモリ・アクセス速度を上回る勢いで向止している。現在の RISC プロセッサでは、大量の 2 次元グラフィックス操作をバスの帯域幅いつばい、ないしそれに近 い速度で実行することが可能であり、もっとも要求の厳しい用途を除けはレンダリング専用 のハードウェアは不要である。本稿では DECstation 3100 および DECstation 5000 / 200 CX のカラー・フレームバッフアのハードウェアと、 X サーバーの実装に使われたいくつか のグラフィックス・アルゴリズムについて述べる。性能測定の結果を示し、メモリ帯域幅と 上交するとともに、フレームバッフアの性能向上におけるもっとも重要な要因をまとめる。 現在、典型的なカラー・ワークステーションのスクリ ーン・サイズは、横 1024 ~ 1280 ピクセル、縦 768 ~ 1 024 ピクセル、 1 ピクセルあたり 8 ピットで、プロ セッサの性能は 1 ~ 3Mips である。従来、大半のカラー ワークステーションは、妥当な性能を得るために専用の グラフィックス・アクセラレータを装備していた。 DECstation 3100 は 1 024X864X8 のカラー・ディ スプレイをサポートしているが、専用のグラフィックス・ ードウェアは備えていない。 MIPS R20001 プロセッ サが、単純なフレームバッフアに直接描画するようにな っている。我々の当初の目標は、 VAXstation 3100 と 同等のグラフィックス性能を得ることにあった。 VAX- station 3100 は 3Mips の処理能力と、技術的にはやや 旧い 2 つのグラフィックス専用チップを備えている。最 終的に、フレームバッフアによってそのチップセット の 2 ~ 4 倍の性能を得ることができた。事実、多くの操 作において、フレームバッフアは現在のグラフィックス・ アクセラレータに匹敵する性能を発揮する。 DECstation 5000 / 200 CX は、 DECstation 3100 の経験にもとづいて作られた。 DECstation 3100 と同 様、 DECstation 5000 の MIPS R3000 もフレーム バッフアに直接描画をする。ピデオ RAM への書込み 1 、、 MIPS 命令セット " は R2000 と R3000 CPU チップのものを 指すが、とくに断らないかぎり、 R6000 チップ・セットおよび将来 の MIPS CPU チップのものも指す。 76 の帯域幅は、ページモードでアクセスするために 2 倍以 上になっている。 本稿では、ピデオメモリ・システムおよび MIPS の命 令セットの特徴のいくつかを論しる。線分とテキストの 描画およびデータのコピーをおこなうグラフィックス・ アルゴリズムにおいて、サーバーか咼速のプロセッサを どのように活用するかを示し、これらのアルゴリズムに よって利用できるメモリの帯域幅を示す。さらに、もっ とも有用な MIPS 命令セットとメモリ・システムの概 略を述べ、フレームバッファおよびグラフィックス・ア クセラレータのそれぞれの長所を論する。 フレームバッフアの構成 DECstation 3100 のカラー・フレームノヾッフアは、 1 , 024 個のピクセル ( 1 ピクセルあたり 8 ヒ、ツト ) から なる 1 024 本のスキャンラインとして構成されている。 ディスプレイのハードウェアは、各ピクセルの値を 256 個のエントリをもつカラーマップへのインデックス値と して使用する。このカラーマップにより、 24 ピットの RGB データがデジタル・アナログ・ヒ、デオコンバータ に渡される。各スキャンラインの最小アドレス ( 下位 10 ビットがすべて 0 ) はスクリーンの左端、最大アドレス ( 下位 10 ピットがすべて 1 ) は右端に対応する。 実際にディスプレイ画面に表示されるのは、最初の UNIX MAGAZINE 1991 ユ 0

X サーパーの高速化 ているわけではない。グリフがきわめて小さいため、コ ンパイラはグリフ・ビットのフェッチに上交的長い時間を かけているからである。 DECstation 5000 上では、サ ーはビデオ RAM ページを頻繁に切り替えるので、 書込みの多くは高速ページモード・サイクルを利用でき ない。また、すでに述べたように、コンパイラは case 分岐に関してはあまり適切でないコードを生成する。 ーは、上記のアルゴリズムをアセンプ カラーサー ノ、 前景 リ・コードを使って実装している。アセンプリ・コードは 既存のビクセル Times-Roman()O ホイント、 75dpi) を DECstation て得たものである。サーバーと xllperf は同じマシン上 3100 上では 64 000 文字 / s 、 DECstation 5000 上では で動かし、 UNIX ソケットを使って通信した。 xllperf 91 , 000 文字 / s で描画する。また、次節で述べる改良を は、サーバーがさまざまなグラフィックスおよびウイン 施すと、 6 x 13 のフォントを DECstation 3100 上で ドウ管理リクエストを実行するために消費した時間を測 は 69 000 文字 / s 、 DECstation 5000 上では 102 000 定する。コードの実行時間測定とチューンのためにこれ 文字 / s で描画するようになる。 をおおいに利用した。 ImageText PoIyText ImageText リクエストは P01yText リクエストに似 ているが、各グリフを不透明ステイプルの手法で描画す PolyText リクエストは文字列をスクリーンに描画す る。サーバーは最初に各文字のフォント固有のグリフ る。同しフォントに属するものでも、グリフによって幅 と高さは異なる。たとえば、文字、、 : " は 2X7 のグリフ ( ビットマップ・ピクチャー ) を参照する。次に、透明ステ にマップされ、文字、、 H " は 5 x 9 のグリフにマップさ イプルの手法で一度に 1 つのグリフを描画する。グリフ れる。各グリフは、概念的にはフォント全体の高さに達 中の 1 のピットに対応する前景ピクセルを描画し、 0 に 対応する書込み先はそのままにしておく。図 10 に、、 Z " するまで 0 のピットを付加して上下に延長され、グリフ の文字コードがどのように描画されるかを示す。 間の隙間は 0 のビットによって埋められる。 ImageText は、おもに、、固定メトリック " フォントを PolyText は、 WYSIWYG ェデイタで頻繁に使われ 使用する端末工ミュレータでの利用を主眼としている。 る。これにより、ユーサーは同し行に異なる高さのフォ このようなフォント中の各グリフは、同じ幅と高さ ( た ントを混在させることができるようになる。これらの工 とえは、 6X13 のなかのグリフはすべて幅が 6 ピット、 デイタではその行のなかでもっとも背の高いフォントに 高さが 13 ビットである ) をもつ。 1 つのフォント ( 可変 合わせて文字の行の背景の矩形を描画する。そして、そ ピッチのものも含む ) しか使えないテキスト・ウインド の背景の上に PolyText で文字を描画する。 ウでも、 ImageText を使用する。 ImageText は、フォ 上記の透明ステイプルの手法を用い、 C 言語による ント中のすべてのグリフを自動的に同し高さに拡大する p 。 lyText の実装をおこなうと、可変ピッチ・フォントの からである。 Times-Roman()0 ポイント、 75dpi) を DECstation ImageText を実装するもっとも簡単な方法は、背景 3100 上では 31 , 000 文字 / s 、 DECstation 5000 上で の矩形をクリアしてから PolyText コードを用いて則景 は 57 , 000 文字 / s で描画する。また、幅と高さを 6X13 ピクセルを描画することである。この単純な手法は驚く に固定したフォントの場合は、 DECstation 3100 では ーはすべての可 38 000 文字 / s 、 DECstation 5000 上では 46 000 文 ほどうまくいく。そして、カラーサー 変ピッチ・フォントをこの方法で描画する。これらのフォ 字 /s になる。 ントにおいて背景と前景を同時に描画するのは難しい。 これらの数値は素晴らしいものであるが、限界を示し 、、 Z " を描画する PolyText 図 10 グリフ・ビットマップ 画面 文字 ロ■ロロ ロロ■ロ ロ■ロロ ロロ■ロ 000 0 00 000 住 0000 ■ ■ 89 UNIX MAGAZINE 1991.10