Archiv verlassen und diese Seite im Standarddesign anzeigen : Anteil "0" und "1" an Code
Dj dicke Brust
2004-09-21, 18:39:14
Hallo Leute
Ich hab mich gerade eben mal gefragt ob es eigentlich Studien darüber gibt wieviel Prozent an Code nullen oder einsen sind. Habe darüber nachgedacht weil ich mir so dachte das der Anteil an nullen recht hoch liegen könnte. Im Umkehrschluss dachte ich daran, um Strom zu sparen, die Wertigkeiten für eins und null einfach umzudrehen und so den Stromverbrauch von chips zu senken.
Gibt es solche überlegungen schon und auch schon techniken die dies einsetzen?
Dj dicke Brust
Freakazoid
2004-09-21, 19:22:18
Hallo Leute
Ich hab mich gerade eben mal gefragt ob es eigentlich Studien darüber gibt wieviel Prozent an Code nullen oder einsen sind. Habe darüber nachgedacht weil ich mir so dachte das der Anteil an nullen recht hoch liegen könnte. Im Umkehrschluss dachte ich daran, um Strom zu sparen, die Wertigkeiten für eins und null einfach umzudrehen und so den Stromverbrauch von chips zu senken.
Gibt es solche überlegungen schon und auch schon techniken die dies einsetzen?
Dj dicke Brust
Wenn der Anteil 0en größer wär, spart man doch nach deiner überlegung
Man spart in keiner Richtung etwas, weder bei 0 noch bei 1 wird mehr Strom verbraucht. Den braucht es nur zum Umschalten zwischen diesen Zuständen.
Aber erst mit CMOS, früher wäre es wirklich so gewesen ;)
Ich weiß auch nicht wie es mit den Leckströmen aussieht, aber ich denke das durch eine "0" im Schnitt genausoviele Transistoren schalten wie durch eine "1" und das deshalb unerheblich ist.
Dj dicke Brust
2004-09-21, 19:51:48
das der strom beim schalten benutzt wird ist wohl richtig. Aber bei DDR-Ram wird doch ständig ein Kondensator aufgeladen damit der Transistor nicht seinen Zustand sagen wir mal eins nicht verliert (oder war das anders?). Also wenn der Anteil an einsen im Code höher wäre liesse sich doch so Strom sparen.
Ob bei Code 0 oder 1 wahrscheinlicher ist, hängt vom Instruktionsset ab. Bei Daten allerdings sind Nullen im Schnitt wahrscheinlicher.
Vedek Bareil
2004-09-21, 21:02:48
Aber erst mit CMOS, früher wäre es wirklich so gewesen ;)da stellt sich mir eine Frage: warum braucht man für CMOS eigentlich Feldeffekt-Transis? Wenn ich mir so ein typisches CMOS-Gatter so angucke, könnte ich mir vorstellen, daß es mit bipolaren Transis doch ebenso funktionieren könnte? Abgesehen davon, daß es dann wohl nur halt nicht CMOS (das MO kommt ja von dem isolierenden Metalloxid zwischen Gate und Kanal) heißen würde...
Aber erst mit CMOS, früher wäre es wirklich so gewesen ;)
Ich weiß auch nicht wie es mit den Leckströmen aussieht, aber ich denke das durch eine "0" im Schnitt genausoviele Transistoren schalten wie durch eine "1" und das deshalb unerheblich ist.
Bei CMOS schalten die Transistoren, die für 0 oder 1 zuständig sind sowieso immer paarweise.
BlackBirdSR
2004-09-21, 21:15:45
da stellt sich mir eine Frage: warum braucht man für CMOS eigentlich Feldeffekt-Transis? Wenn ich mir so ein typisches CMOS-Gatter so angucke, könnte ich mir vorstellen, daß es mit bipolaren Transis doch ebenso funktionieren könnte? Abgesehen davon, daß es dann wohl nur halt nicht CMOS (das MO kommt ja von dem isolierenden Metalloxid zwischen Gate und Kanal) heißen würde...
Bipolar hatte man früher.
Die elektrischen Eigenschaften sind echt mies für so hohe Integration.
Ausserdem kann man Bipolar nur schwer so dicht packen wie CMOS.
Bis zum Pentium waren es sogar noch BICMOS Prozesse ;)
Pinoccio
2004-09-21, 21:20:27
Ob bei Code 0 oder 1 wahrscheinlicher ist, hängt vom Instruktionsset ab. Bei Daten allerdings sind Nullen im Schnitt wahrscheinlicher.
Ein Code der deutlich mehr 0 oder 1 enthält ist aber nicht unbedingt gut, oder?
Und wieso ist bei Daten die 0 häufiger? Benfords Gestz? (http://www.kmkorn.de/sw/benford/benford.htm)
mfg Sebastian
Ein Code der deutlich mehr 0 oder 1 enthält ist aber nicht unbedingt gut, oder?
Völlig egal. Nach dem Decode ist eh alles anders.
Und wieso ist bei Daten die 0 häufiger? Benfords Gestz?
Man betrachtet ja nicht die Anfangsziffer sondern jedes Bit.
Aber z.B. bei Text fallen sehr viel mehr Werte in einem bestimmten Bereich unter 128 an, wodurch zwangsläufig immer eine 0 mehr pro Byte entsteht im Durchschnitt.
Pinoccio
2004-09-21, 21:58:41
Völlig egal. Nach dem Decode ist eh alles anders.
Man betrachtet ja nicht die Anfangsziffer sondern jedes Bit.
Aber z.B. bei Text fallen sehr viel mehr Werte in einem bestimmten Bereich unter 128 an, wodurch zwangsläufig immer eine 0 mehr pro Byte entsteht im Durchschnitt.
Es geht ja um das, was nach dem decoden direkt in die Rechenwerke kommt, nicht um C-Quelltexte oder ASM, sondern um Micro-ops (wie immer die auch bei AMD heißen mögen).
Hm, müsste man mal ein kleines Progrämmchen über seine Festplatte jagen, anyone? :idea:
mfg Sebastian
GloomY
2004-09-21, 22:41:57
Bei Daten allerdings sind Nullen im Schnitt wahrscheinlicher.Aber z.B. bei Text fallen sehr viel mehr Werte in einem bestimmten Bereich unter 128 an, wodurch zwangsläufig immer eine 0 mehr pro Byte entsteht im Durchschnitt.Von Text einmal abgesehen stellt sich die Frage, ob das bei den restlichen Daten auch der Fall ist. Wie sieht es bei Zahlen (Integer oder FP) aus? Sind dort kleine Zahlenbereiche auch wahrscheinlicher?
Bei Integer enthalten kleine positive Zahlen mehr Nullen, jedoch kleine negative Zahlen Dank des Zweier-Komplementes mehr Einsen. Bei FP sollte bei Zahlen mit kleinem Betrag der Exponent eigentlich immer sowas wie 100000... (2^0) sein, also mehr Nullen als Einsen. Da die Mantisse wohl gleichverteilt Einsen und Nullen enthält, wären es insgesamt mehr Nullen als Einsen...
Btw: Das Pentium 4 Busprotokoll benutzt einen Trick, indem es die Anzahl der sich ändernden 0->1 bzw. 1->0 Übergänge auf jeder Datenleitung von jedem Takt auf den nächsten zählt. Wenn sich bei mehr als der Hälfte die Bitzustände ändern, dann wird auf einer speziellen Steuerleitung ein Signal gesetzt und alle Datenleitungen werden invertiert. Der Empfänger kann dann mit Hilfe dieser Steuerleitung die Daten wieder rück-invertieren. Dadurch erreicht man, dass sich nie mehr als die Hälfte der Bits von einem Takt auf den anderen ändern.
Ob das nur bei den Datenleitungen so gemacht wird oder ob das auch die Adressleitungen betrifft, habe ich allerdings nicht mehr so genau im Kopf...
Es geht ja um das, was nach dem decoden direkt in die Rechenwerke kommt, nicht um C-Quelltexte oder ASM, sondern um Micro-ops (wie immer die auch bei AMD heißen mögen).
Ja, das wirst du aber nie zu gesicht bekommen auf der Festplatte.
Von Text einmal abgesehen stellt sich die Frage, ob das bei den restlichen Daten auch der Fall ist. Wie sieht es bei Zahlen (Integer oder FP) aus? Sind dort kleine Zahlenbereiche auch wahrscheinlicher?
Ja, wie du dann auch selbst überlegt hast. Benfords Gesetz spielt in der Tat noch mit rein, sofern man Daten hat.
GloomY
2004-09-21, 23:41:45
Ja, wie du dann auch selbst überlegt hast.Ich habe überlegt, dass es bei betragsmäßig kleinen Zahlen wohl mehr Nullen als Einsen sind. Ob man aber davon ausgehen kann, dass Daten - abgesehen von Text - verstärkt betragsmäßig kleine Zahlen beinhalten, ist aber noch nicht geklärt.
Benfords Gesetz spielt in der Tat noch mit rein, sofern man Daten hat.Dieses bezieht sich doch nur auf die allererste Stelle und nicht auch noch auf den Rest. Im Binärsystem sollte das Gesetz doch eh wenig, wenn nicht sogar keinen Einfluss, haben.
Ich habe überlegt, dass es bei betragsmäßig kleinen Zahlen wohl mehr Nullen als Einsen sind. Ob man aber davon ausgehen kann, dass Daten - abgesehen von Text - verstärkt betragsmäßig kleine Zahlen beinhalten, ist aber noch nicht geklärt.
Üblicherweise schon, da du den Wertebereich für Integer-Zahlen nur in großen Schritten festlegen kannst, und positive Zahlen auch öfter vorkommen als negative. Somit werden sehr häufig "Füllbits" gebraucht, wo z.B. 10 oder 20 Bits ausreichen würden.
Bipolar hatte man früher.
Die elektrischen Eigenschaften sind echt mies für so hohe Integration.
Ausserdem kann man Bipolar nur schwer so dicht packen wie CMOS.
Bis zum Pentium waren es sogar noch BICMOS Prozesse ;)
Aber auch nur die Treiber waren Bipolar, den Rest auch Bipolar zu machen, hätte damals schon Unsinn bedeutet.
Ich habe überlegt, dass es bei betragsmäßig kleinen Zahlen wohl mehr Nullen als Einsen sind. Ob man aber davon ausgehen kann, dass Daten - abgesehen von Text - verstärkt betragsmäßig kleine Zahlen beinhalten, ist aber noch nicht geklärt.Das ist aber so.
Dieses bezieht sich doch nur auf die allererste Stelle und nicht auch noch auf den Rest. Im Binärsystem sollte das Gesetz doch eh wenig, wenn nicht sogar keinen Einfluss, haben. Das bezieht sich auch auf die zweite, dritte und vierte, auf jede Stelle, wenn dabei auch der Effekt abnimmt. Es ist egal, wo du Daten erhebst: Ob die Größe von Bergen, ob die digitalisierten Samples einer Audioaufnahme: Kleine Werte sind in der Überzahl.
Pinoccio
2004-09-23, 13:00:27
Aber auch nur die Treiber waren Bipolar, den Rest auch Bipolar zu machen, hätte damals schon Unsinn bedeutet.
Also es gibt ja bipolare Treiber, aber es geht hier bei bipolar eher um
sowas (http://www.winhelpline.info/news/kommentar.php?id=8719) (unterster Abschnitt). Interessant wäre es zu wissen, was genau du meinst.
/edit: @Gast hierdrunter: Danke! Wieder was gelernt!
Zum Topic: Mag nicht einer mal ein kleines Zählprogramm schreiben?
Wobei: ein komprimiertes Video zB hatt im Idealfall ja hälfte-hälft, aber im Prozessor wird es ja decodiert, also müsste man erstmal festlegen, was genau gezählt wird und wo, und wie das dann geht.
mfg Sebastian
Interessanter Link (http://www.striker.ottawa.on.ca/~aland/isreal/)
Also es gibt ja bipolare Treiber, aber es geht hier bei bipolar eher um
sowas (http://www.winhelpline.info/news/kommentar.php?id=8719) (unterster Abschnitt). Interessant wäre es zu wissen, was genau du meinst.
Interessanter Link (http://www.striker.ottawa.on.ca/~aland/isreal/)
Die Treiber sind die In/Output Schaltungen der Chips. Durch die langen Wege auf dem Mainboard (Frequenzeigenschaften) und den enormen Stromfluss sind die "Treiberschaltungen" oft aus Bipolaren Transistoren ausgelegt.
Die eigendliche Rechenlogic bleibt dabei CMOS oder NMOS Technik vorbehalten.
HellHorse
2004-09-23, 21:37:51
Zum Topic: Mag nicht einer mal ein kleines Zählprogramm schreiben?
:|
Bei dem Link, den du gepostet hast, gabs das:
http://www.kmkorn.de/sw/benford/benfordlaw_v_0_2.zip
Pinoccio
2004-09-23, 22:09:42
:|
Bei dem Link, den du gepostet hast, gabs das:
http://www.kmkorn.de/sw/benford/benfordlaw_v_0_2.zip
Ich kann leider nicht nachprüfen was das Program macht, aber laut Beschreibung auf der Hompage:
"Das Script berechnet aus den Dateigrößen die Häufigkeit der ersten Ziffer". :P
Darum geht es ja schon gar nicht mehr.
mfg Sebastian
HellHorse
2004-09-24, 00:07:30
Ok, Strafe muss wohl sein:
#! /usr/bin/python
from sys import argv
def countones(number):
found = 0
while number:
div, rest = divmod(number, 2)
if rest:
found += 1
number = div
return found
def analyseFile(fileName):
print "analysing file %s" % fileName
zeros, ones = 0, 0
f = file(fileName, 'r')
nextByte = f.read(1)
while nextByte:
foundOnes = countones(ord(nextByte))
zeros += 8 - foundOnes
ones += foundOnes
nextByte = f.read(1)
f.close
print "zeros: %(zeros)s ones: %(ones)s" % locals()
if __name__ == "__main__":
[analyseFile(fileName) for fileName in argv[1:]]
Pinoccio
2004-09-24, 01:06:09
Ok, Strafe muss wohl sein
Respekt! (wobei es sicher nicht so beeindruckend aussieht, wenn man Perl/Phyton/*wasistdas?* kann! ;-)
Was sagt das nette Programm den zu den Datein auf deiner Festplatte, das würde mich fast noch mehr interessieren?
Gute Nacht! (mal sehen ob ich Null jetzt nur Eins träume! ;-D)
mfg Sebastian
HellHorse
2004-09-24, 12:28:47
Das Skript ist verdammt langsam, vermutlich aufgrund der Divisionen und modulo Operationen.
Die ganze Festplatte scannen scheidet also aus.
kernel image
0en: 6'238'718
1en: 6'386'306
ein zufälliges movie
0en: 8'610'330
1en: 6'831'070
source files im aktuellen Verzeichnis
0en: 401'386
1en: 303'782
kernel object files
0en: 29'865'167
1en: 15'307'129
Immer vorausgesetzt das Skript arbeitet korrekt ;)
Pinoccio
2004-09-26, 17:13:28
Das Skript ist verdammt langsam, vermutlich aufgrund der Divisionen und modulo Operationen.
Die ganze Festplatte scannen scheidet also aus.
Hm, nette Zahlen, etwas überaschend!
Werde mal sehen, wenn ich Zeit finde das mal selbst zu erforschen auf meiner Festplatte, vielleicht ist unter Windows ja alles anders ... ;-)
mfg Sebastian
HellHorse
2004-09-27, 11:23:53
Ja, aber wenn du dir einen Gefallen tun willst, dann nimm nicht das Skript.
Warum? "verdammt langsam" heisst in dem Fall 188 KB/s und das ist im Gegensatz zur geposteten Version, eine "optimierte" die eine lut verwendet. =)
Habe das ganze nach Java protiert und hatte auf Anhieb 14 MB/s auf einer stärkeren Kiste sogar 25 MB/s.
Ja, aber wenn du dir einen Gefallen tun willst, dann nimm nicht das Skript.
Warum? "verdammt langsam" heisst in dem Fall 188 KB/s und das ist im Gegensatz zur geposteten Version, eine "optimierte" die eine lut verwendet. =)
Die kann aber nicht besonders optimiert sein ;)
Auf meinem Pentium-M 1,5GHz schaffe ich 1,5 MiB/s damit:
import sys
import os
import time
if __name__ == '__main__':
if len(sys.argv) < 2:
print "Aufruf mit Dateinamen als Parameter"
sys.exit()
# Setze Zaehler fuer Bytes auf 0
startTime = time.clock()
byteCounter = [ 0 ] * 256
# LUT erstellen, die die Anzahl 1en fuer alle Bytes enthaelt
bitLUT = [ 0 ]
for i in range(8):
bitLUT += [ b + 1 for b in bitLUT ]
# Datei lesen
daten = file(sys.argv[1], "rb").read()
# fuer jedes Byte entsprechenden byteCounter erhoehen ("inner loop")
for c in daten:
byteCounter[ord(c)] += 1
# Anzahl der 1en feststellen
numOnes = 0
for i in range(256):
numOnes += byteCounter[i] * bitLUT[i]
numZeroes = len(daten) * 8 - numOnes
print "Bytes: %d, Einsen: %d, Nullen: %d" % (len(daten), numOnes, numZeroes)
print "Zeit: %f s" % (time.clock() - startTime)
HellHorse
2004-09-28, 00:59:41
Die kann aber nicht besonders optimiert sein ;)
IO wars natürlich (es musste IO sein, es war klar dass es IO war, es konnte nur IO sein, ... ;) ). Obwohl ich nicht ganz sicher bin, wie toll es es sich mit richtig grossen Files verhält.
Jetzt ist's etwa gleich schnell, allerdings heisst das auf dieser lamen Kist hier bloss ~670 KB/s. :(
Update:
Nun zu dir ;)
Geniale Art die LUT zu berechnen :respekt:
Der byteCounter ist sehr praktisch, frisst aber auch etwas Leistung weg (nicht viel).
Nachdem ich an meinen Skipt etwas rumgebastelt hatte, war ich auf einmal fast doppelt so schnell (wie dein Skript). Das verwunderliche daran war, dass ich eigentlich das Gleiche mache, bloss nicht alles in einem Block. Also habe ich deinen Code mal etwas umgestellt, und dabei kam das raus:
#! /usr/bin/python
import sys, os, time
def analyse_file():
# Datei komplett lesen
f = file(sys.argv[1], "rb")
daten = f.read()
f.close()
return analyse_stirng(daten)
def analyse_stirng(daten):
# LUT erstellen, die die Anzahl 1en fuer alle Bytes enthaelt
bitLUT = [ 0 ]
for i in xrange(8):
bitLUT += [ b + 1 for b in bitLUT ]
numOnes = 0
# fuer jedes Byte die Anzahl 1en erhoehen ("inner loop")
for c in daten:
numOnes += bitLUT[ord(c)]
# Anzahl der 0en berechnen
numZeroes = len(daten) * 8 - numOnes
return numZeroes, numOnes
if __name__ == '__main__':
if len(sys.argv) < 2:
print "Aufruf mit Dateinamen als Parameter"
sys.exit()
startTime = time.clock()
numZeroes, numOnes = analyse_file()
print "Bytes: %d, Einsen: %d, Nullen: %d" % ((numZeroes + numOnes) * 8, numOnes, numZeroes)
print "Zeit: %f s" % (time.clock() - startTime)
Bis auf den fehlenden byteCounter macht es das gleiche, ist bei mir aber 2 mal so schnell (Python 2.3.4 auf Linux). Dabei kam der grösste Anteil (etwa 80 %) vom Aufteilen und nicht vom Weglassen des byteCounter.
Kannst du das bestätigen? Hast du eine Erklärung dafür?
Bis auf den fehlenden byteCounter macht es das gleiche, ist bei mir aber 2 mal so schnell (Python 2.3.4 auf Linux). Dabei kam der grösste Anteil (etwa 80 %) vom Aufteilen und nicht vom Weglassen des byteCounter.
Kannst du das bestätigen? Hast du eine Erklärung dafür?
Kann ich bestätigen (Python 2.3 Win32). In der ursprünglichen Version war bei mir der byteCounter sogar minimal schneller, aufgeteilt ist er langsamer. Jetzt komme ich auf 2,7MiB/s.
Aus irgendeinem nicht mehr nachzuvollziehenden Grund dachte ich dass der ständige Zugriff auf die bitLUT langsamer wäre, aber byteCounter ist in dieser Hinsicht ja identisch, und benötigt einen kompletten Read-Modify-Write-Cycle. Das ist natürlich dumm, eine einzelne Summe kann immer in einem Register gehalten werden.
Es ist wohl so dass der Interpreter Code auf globaler Ebene kaum optimiert, weil er annimmt dass der sowieso nur einmal ausgeführt wird, während bei Funktionen mehrmaliger Aufruf angenommen wird.
DocEW
2004-10-05, 07:04:27
# LUT erstellen, die die Anzahl 1en fuer alle Bytes enthaelt
bitLUT = [ 0 ]
for i in range(8):
bitLUT += [ b + 1 for b in bitLUT ]
Kannst du das mal erklären? Ich kenne Python nicht und raff's einfach nicht. Hoffe das ist nicht zu OT, sorry...
Schau dir mal folgende Auflistung an:
0
1
10
11
100
101
110
111
wenn du das fortsetzen wolltest, würdest du alle 8 bisherigen Zahlen nehmen, und eine 1 davor stellen. Dann hast du 16 Zahlen. Dann nimmst du wieder alle 16 bisherigen Zahlen, und stellst eine 1 davor, usw.
Mein Code macht genau das, er beginnt mit einer Liste, die nur das Element 0 enthält, und durchläuft achtmal eine Schleife, in der alle Elemente der Liste um 1 erhöht und wieder ans Ende der Liste angehängt werden.
Aus [ 0 ] wird [ 0, 0+1 ], also [ 0, 1 ]
Aus [ 0, 1 ] wird [ 0, 1, 0+1, 1+1 ], also [ 0, 1, 1, 2 ]
Aus [ 0, 1, 1, 2 ] wird [ 0, 1, 1, 2, 1, 2, 2, 3 ]
Aus [ 0, 1, 1, 2, 1, 2, 2, 3 ] wird [ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 ], etc.
Und das sind genau die Anzahl der gesetzten Bits der entsprechenden Binärzahlen.
DocEW
2004-10-05, 21:31:40
Wow. WOW! *Ziemlich* clever! =)
Vielen Dank für die Erklärung auch!
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.