ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6679
Скачиваний: 8
Алфавитный список литературы 6 6 3
137.
Solomon, DA.
Inside Windows NT, 2nd ed., Redmond, WA: Microsoft Press, 1998.
138.
Sprangle, E., Chappell, R. S., Alsup, M., and Patt, Y. N.
«The Agree Predictor: A
Mechanism for Reducing Negative Branch History Interference», Proc. 24th Ann.
Int'l. Symp. on Computer Arch., ACM, p. 284-291,1997.
139.
Stallings, W.
Computer Organization and Architecture, 4th ed. Upper Saddle
River, NJ: Prentice Hall, 1996.
140.
Stenstrom, P., Hagersten, E., Lilja, D.J., Martonosi, M., and Venugopal, M.
«Trends
in Shared Memory Multiprocessing», IEEE Computer Magazine, vol. 30, p. 44-
50, Dec. 1997.
141.
Stets, K, Dwarkadas, S., HardaveUas, N, Hunt, G., Kontothanassis, L, Parthasarathy, S.,
and Scott, M.
«CASHMERE-2L: Software Coherent Shared Memory on Clus-
tered Remote-Write Networks», Proc. 16th Symp. on Operating Systems Prin-
ciples, ACM, p. 170-183, 1997.
142.
Sunderram, V. B.
«PVM: A Framework for Parallel Distributed Computing»,
Concurrency: Practice and Experience, vol. 2, p. 315-339, Dec. 1990.
143.
Swan, R.J., Fuller, S. H., andSiewiorek, D. P.
«Cm* —A Modular Multiprocessor»,
Proc. NCC, p. 645-655,1977.
144.
Tan, W. M.
Developing USB PC Peripherals, San Diego, CA: Annabooks, 1997.
145.
Tanenbaum, A. S.
«Implications of Structured Programming for Machine
Architecture», Commun. of the ACM, vol. 21, p. 237-246, Mar. 1978.
146.
Tanenbaum, A. S., and Woodhull, A. W.
Operating Systems: Design and Imple-
mentation, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 1997.
147.
Thompson, K.
«UNIX Implementation», Bell Syst. Tech. J., vol. 57, p. 1931-1946,
July-Aug. 1978.
148.
Treleaven, P.
«Control-Driven, Data-Driven, and Demand-Driven Computer
Architecture», Parallel Computing, vol. 2, 1985.
149.
Tremblay, M. and О 'connorj. M.
«UltraSPARC I: A Four-Issue Processor Sup-
porting Multimedia», IEEE Micro Magazine, vol. 16, p. 42-50, April 1996.
150.
Triebel, W. A.
The 80386, 80486, and Pentium Processor, Upper Saddle River,
NJ: Prentice Hall, 1998.
151.
linger, S. H.
«A Computer Oriented Toward Spatial Problems», Proc. IRE, vol. 46,
p. 1744-1750,1958.
152.
Vahalia, U.
UNIX Internals, Upper Saddle River, NJ: Prentice Hall, 1996.
153.
Van DerPoel, W. L.
«The Software Crisis, Some Thoughts and Outlooks», Proc.
IFIP Congr. 68, p. 334-339, 1968.
6 6 4 Глава 9. Библиография
154.
Van Steen, M., Homburg, P. C, and Tanenbaum, A. S.
«The Architectural Design
of Globe: A Wide-Area Distributed System», IEEE Concurrency, vol. 7, p. 70-
78Jan.-March 1999.
155.
Verstoep, K., Langedoen, K., andBal, H. E.
«Efficient Reliable Mulicast on Myri-
net», Proc. 1996 Int'l. Conf. on Parallel Processing, IEEE, p. 156-165,1996.
156.
Weaver, D. L., and Germond, T.
The SPARC Architecture Manual, Version 9,
Englewood Cliffs, NJ: Prentice Hall, 1994.
157.
mikes, M. V.
«Computers Then and Now», J. ACM, vol. 15, p. 1-7, Jan. 1968.
158.
Wilkes, M. V.
«The Best Way to Design an Automatic Calculating Machine»,
Proc. Manchester Univ. Computer Inaugural Conf., 1951.
159.
Wilkinson, B.
Computer Architectural Design and Performance, 2nd ed., Engle-
wood Cliffs, NJ: Prentice Hall, 1994. Wilinson, 1994.
160.
Wilkinson, B. and Allen, M.
-arallel Programming: Techniques and Applications
Using Networked Workstations and Parallel Computers, Upper Saddle River,
NJ: Prentice Hall, 1999.
161.
Wilson, J.
«Challenges and Trends in Processor Design», IEEE Computer Maga-
zine, vol. 31, p. 39-48, Jan. 1998.
162.
Wilson, P.
«Floating-Point Survival Kit», Byte, vol. 13, p. 217-226, March 1988.
163.
Yeh, T.-Y., and Pott, Y. -N.
«Two-Level Adaptive Training Branch Prediction»,
Proc. 24th Int'l. Symp. on Microarchitectwe, ACM/IEEE, p. 51-61,1991.
Приложение А
Двоичные числа
Арифметика, применяемая в компьютерах, сильно отличается от арифметики, ко-
торая используется людьми. Во-первых, компьютеры выполняют операции над
числами, точность которых конечна и фиксирована. Во-вторых, в большинстве
компьютеров используется не десятичная, а двоичная система счисления. Этим
двум проблемам и посвящено приложение.
Числа конечной точности
Когда люди выполняют какие-либо арифметические действия, их не волнует во-
прос, сколько десятичных разрядов занимает то или иное число. Физики, к приме-
ру, могут вычислить, что во Вселенной присутствует 10
78
электронов, и их не вол-
нует тот факт, что полная запись этого числа потребует 79 десятичных разрядов.
Никогда не возникает проблемы нехватки бумаги для записи числа.
С компьютерами дело обстоит иначе. В большинстве компьютеров количество
доступной памяти для хранения чисел фиксировано и зависит от того, когда был
разработан этот компьютер. Если приложить усилия, программист сможет пред-
ставлять числа в два, три и более раз большие, чем позволяет размер памяти, но
это не меняет природы данной проблемы. Память компьютера ограничена, поэто-
му мы можем иметь дело только с такими числами, которые можно представить
в фиксированном количестве разрядов. Такие числа называются
числами конеч-
ной точности.
Рассмотрим ряд положительных целых чисел, которые можно записать тремя
десятичными разрядами без десятичной запятой и без знака. В этот ряд входит
ровно 1000 чисел: 000, 001, 002, 003,..., 999. При таком ограничении невозможно
выразить определенные типы чисел. Сюда входят:
1. Числа больше 999.
2. Отрицательные числа.
3. Дроби.
4. Иррациональные числа.
6 6 6 Приложение А. Двоичные числа
5. Комплексные числа.
Одно из свойств набора всех целых чисел — замкнутость по отношению к опе-
рациям сложения, вычитания и умножения. Другими словами, для каждой пары
целых чисел
i nj
числа
i+j, i-j
и
ixj
— тоже целые числа. Ряд целых чисел не замк-
нут относительно деления, поскольку существуют такие значения
г nj,
для кото-
рых
i/j
не выражается в виде целого числа (например, 7/2 или 1/0).
Числа конечной точности не замкнуты относительно всех четырех опера-
ций. Ниже приведены примеры операций над трехразрядными десятичными
числами:
600+600=1200 (слишком большое число);
003-005=-2 (отрицательное число);
050x050=2500 (слишком большое число);
007/002=3,5 (не целое число).
Отклонения можно разделить на два класса: операции, результат которых пре-
вышает самое большое число ряда (ошибка переполнения) или меньше, чем самое
маленькое число ряда (ошибка из-за потери значимости), и операции, результат
которых не является слишком маленьким или слишком большим, а просто не яв-
ляется членом ряда. Из четырех примеров, приведенных выше, первые три отно-
сятся к первому классу, а четвертый — ко второму классу.
Поскольку размер памяти компьютера ограничен и он должен выполнять ариф-
метические действия над числами конечной точности, результаты определенных
вычислений будут неправильными с точки зрения классической математики. Вы-
числительное устройство, которое выдает неправильный ответ, может показаться
странным на первый взгляд, но ошибка в данном случае — это только следствие
его конечной природы. Некоторые компьютеры содержат специальное аппарат-
ное обеспечение, которое обнаруживает ошибки переполнения.
Алгебра чисел конечной точности отличается от обычной алгебры. В качестве
примера рассмотрим ассоциативный закон
a+(b-c)=(a+b)-c.
Вычислим обе части выражения для а=700, 6=400 и с=300. В левой части сна-
чала вычислим значение
(b-с).
Оно равно 100. Затем прибавим это число К Й И
получим 800. Чтобы вычислить правую часть, сначала вычислим
(а+Ь).
Для трехразрядных целых чисел получится переполнение. Результат будет за-
висеть от компьютера, но он не будет равен 1100. Вычитание 300 из какого-то чис-
ла, отличного от 1100, не даст результата 800. Ассоциативный закон не имеет силы.
Порядок операций важен.
Другой пример — дистрибутивный закон:
ах (b-c)=axb-axc.
Сосчитаем обе части выражения для
а=5,
6=210 и с= 195. В левой части 5х 15=75.
В правой части 75 не получается, поскольку
axb
выходит за пределы ряда.
Исходя из этих примеров, кто-то может сделать вывод, что компьютеры совер-
шенно непригодны для выполнения арифметических действий. Вывод, естествен-
Позиционные системы счисления 667
но, неверен, но эти примеры наглядно иллюстрируют важность понимания, как
работает компьютер и какие ограничения он имеет.
Позиционные системы счисления
Обычное десятичное число состоит из цепочки десятичных разрядов и иногда
десятичной запятой. Общая форма записи показана на рис. А. 1. Десятка выбрана
в качестве основы возведения в степень (это называется
основанием системы
счисления),
поскольку мы используем 10 цифр. В компьютерах удобнее иметь дело
с другими основаниями системы счисления. Самые важные из них — 2, 8 и 16.
Соответствующие системы счисления называются
двоичной, восьмеричной
и
шест-
надцатеричной
соответственно.
Сотни Десятки Единицы Десятые Сотые Тысячные
d
n
...
62
d-| d
0
• d_i d-2 d-
3
... d.|<
n
Число =Ed|x10'
l=-k
Рис. А. 1. Общая форма десятичного числа
&-ичная система требует
k
различных символов для записи разрядов с 0 по
k—
1.
Десятичные числа строятся из 10 десятичных цифр
0 1 2 3 4 5 6 7 8 9
Двоичные числа, напротив, строятся только из двух двоичных цифр
01
Восьмеричные числа состоят из восьми цифр
0 1 2 3 4 5 6 7
Для шестнадцатеричных чисел требуется 16 цифр. Это значит, что нам нужно
6 новых символов. Для обозначения цифр, следующих за 9, принято использовать
прописные латинские буквы от А до F. Таким образом, шестнадцатеричные числа
строятся из следующих цифр.
0 1 2 3 4 5 6 7 8 9 A B C D E F
Двоичный разряд (то есть 1 или 0) обычно называют
битом.
На рис. А.2 десятич-
ное число 2001 представлено в двоичной, восьмеричной и шестнадцатеричной
системе. Число 7В9 очевидно шестнадцатеричное, поскольку символ В встречается
только в шестнадцатеричных числах. А число 111 может быть в любой из четырех
систем счисления. Чтобы избежать двусмысленности, нужно использовать индекс
для указания основания системы счисления.