On Thu, 2010-10-28 at 17:35 -0400, William Case wrote: > Thank you Marko and Patrick: > > On Thu, 2010-10-28 at 21:36 +0100, Marko Vojinovic wrote: > > On Thursday, October 28, 2010 19:27:16 William Case wrote: > > > How does the cpu search and find stuff? > > > > > > There is a huge amount of searching and finding of text in > > > memory, conditional statements requiring comparisons, and the use of > > > entry points but not exact addresses from within both kernel space and > > > user space. It has occurred to me that a there is necessarily a lot of > > > physical or bit comparing going on. Too much, I would think, to keep > > > dumping a search criteria into a cpu register and then replacing the > > > contents of a second register from a block of memory until one matches. > > > > Believe it or not, in a nutshell that's exactly what is happening. When a > > processor needs to "search" for something in memory, it typically does a > > conditional loop --- load the number from memory into the register (the MOV > > assembly instruction), compare it to the wanted value in the second register > > (CMP), if they are the same break the loop (LOOPNE), otherwise load the next > > number and repeat. > > > > Why do you think there is "too much" of that comparison going on? > > > > I didn't think there was too much from my point of view. I thought > there might be too much from an engineer's perspective. As I have dug > into the inner workings of computers over the last few years, I have > become enthralled with the ingenuity, if not down right genius, of how > computers have been designed and improved over the years -- starting > with basic circuits and instruction sets. I thought I might have missed > something -- missed an aha! moment. In my mind. there was a good chance > that some engineer somewhere had seen the repetition involved in a > search and comparison and developed something quite cunning to shorten > the process. As I said, I always look for the eureka's. > > > > Is there a special unit within the cpu or memory were rapid comparison, > > > or partial comparisons are made during a search, before a criteria is > > > noted as found and moved into the cpu registers? In a generalized way, > > > at the hardware level, how are searched for criteria found? > > > > There is no special unit, AFAIK. You load the two numbers (to be compared) > > into the processor registers, and do a CMP instruction. The processor > > basically subtracts the two numbers, and modifies the flag register according to > > whether the result is positive, negative or zero. The next instruction (say, > > LOOPNE) inspects the flag register and decides what will be the following > > instruction, based on the contents of the flags. This "deciding" amounts to > > changing the value of the IP (instruction pointer) register to one or the > > other predefined value. > > > > You might want to learn a bit of assembly language, if you wish to understand > > basic low-level operations of the processor. And if you want to understand the > > concepts of how processors actually work and what is a computer program in > > principle, you can start from here > > > > http://en.wikipedia.org/wiki/Turing_machine > > I have looked at a Turing Machine and assembly language. Enough to have > a comfortable overview without developing a strong desire or need to dig > deeper. Even spent a couple of afternoons with IA-32 just to take away > the mystery. > > > > but don't curse me later for pointing you to that page. You asked for it! ;-) > > > > > I have googled for an answer and found nothing helpful. That usually > > > means I have somehow mis-posed the question, am working from wrong > > > assumptions or lack the correct terminology. Help chasing the > > > 'searching' mechanism would be appreciated. > > > > Searching "mechanism" is a software algorithm that I described above --- pick > > a value from memory, compare it to the one you search for. If they are the > > same, you found it. If not, pick the next value from memory and repeat. > > > > There is nothing about searching (per se) that is implemented in hardware. The > > processor knows how to move numbers (to registers and memory), how to add > > them, subtract, multiply, divide, compare and jump to the next instruction. > > And that's about it. Everything else is built from that, through various > > algorithms. > > > > Note that this instruction set I described above is not minimal --- for > > example, you can perform multiplication by looping addition (3x2 = 2+2+2). > > Depending how the processor is designed, it can have more or less of these > > non-essential instructions implemented in hardware. You can read on CISC > > versus RISC philosophy here: > > > > http://en.wikipedia.org/wiki/RISC > > > > But I've never heard of a processor that has a "search" instruction > > implemented in hardware. :-) > > > > HTH, :-) > > Marko > > > > -- > Regards Bill > Fedora 13, Gnome 2.30.2 > Evo.2.20.2, Emacs 23.2.1 There has been some work along these lines with something called Content Addressable Parallel Processors. But there are limitations even there. As the content addressable lines are in essence a parallel bus or can be implemented by a high speed serial buss that all the processors listen to, and the interrupt is a serial line that is daisy chained in most implementations, the intermediate responses still require a single processor that answers the interrupts and checks the remainder of the response. Further, this is a specialized search and retrieval architecture, and as such it is more or less a dedicated architecture. That is not bad, but it is expensive relative to the total task a typical processor has to perform. Moreover each unit on the line is a processor in itself, which is a relatively expensive implementation for a memory array. But it did see sufficient interest that I think the 386 processor had some dedicated lines to use for that type of machine design. I haven't heard much about it lately. Modern hash, tree, and segmented search routines, along with relational data base development can nearly equal the performance with lower cost and a more universal architecture, depending on the database implementation, and of course, a universal architecture can be setup to perform the CAPP algorithm using a widely distributed architecture. At least that is my view for what it is worth. Regards, Les H -- users mailing list users@xxxxxxxxxxxxxxxxxxxxxxx To unsubscribe or change subscription options: https://admin.fedoraproject.org/mailman/listinfo/users Guidelines: http://fedoraproject.org/wiki/Mailing_list_guidelines
