Computing desk
< September 14	<< Aug \| September \| Oct >>	September 16 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 15

Old GPU pipeline vs programmable shaders

With the development of GPUs from a fixed pipeline to programmable shaders, how is backwards compatibility maintained? i.e. How can old games still be run on newer PCs? --178.208.200.74 (talk) 00:23, 15 September 2014 (UTC)[reply]

Generally, the old functionality is simply implemented with shaders that the graphics library (Direct3D or OpenGL) generates as needed 'behind the scenes'. There are a few old features that have been abandoned however, so very old games may no longer work for one reason or another. Another problem is that some older games may rely on incorrect assumptions that were never strictly legal, but did work on all hardware at the time. One example of that that I've seen is that when you swap the display buffer (glSwapBuffers), the buffer you get has content that is described in the OpenGL API as "undefined" - but in the early days of 3D rendering, in practice, it would reliably contain the previous image that you generated. Some games would rely on this - even though the API specification said that it wasn't safe to do that. Nowadays, that assumption fails nearly 100% of the time. SteveBaker (talk) 00:31, 15 September 2014 (UTC)[reply]

I'm not sure what you mean by implemented behind the scenes. The games code said to do something which would work on the old hardware. How would a newer GPU know what to do with the old code --178.208.200.74 (talk) 00:37, 15 September 2014 (UTC)[reply]

It's the video driver's job to translate the OpenGL calls into something the GPU will understand. If the GPU only supports programmable shaders, but the client application is using a fixed-function pipeline, the video driver will give the GPU a shader that emulates the fixed-function pipeline of older GPUs. This happens "behind the scenes" (the client application doesn't need to know about it). -- BenRG (talk) 02:25, 15 September 2014 (UTC)[reply]

Ok so then Openggl (and Directx I assume and even things like CUDA and OpenCL) functions get passed to the driver. But the source for an opengl program will be written in C or whatever with libraries that implement the opengl functions. So how is it compiled. Normal C statements like x = a + b would become assembly that moves data into registers performs an add etc. What exactly does a opengl function compile to? --178.208.200.74 (talk) 02:46, 15 September 2014 (UTC)[reply]

If you're asking what the instruction set architecture of the GPU is, it's usually a quite horrible, highly-proprietary, fairly-specific-to-each-model machine language that contains highly specialized instructions to control the primitive operations of graphics processing. A compiler for this architecture is typically provided by the graphics processor vendor, and the audience for said compiler is usually very limited - i.e. that very small community of software people who write drivers for each specific piece of hardware. Most end-users receive the resulting "finished product" in the form of a graphics driver provided by the operating system software vendor, or distributed by the GPU vendor.

For example, i386 or x86_64 are names for two broad Intel CPU instruction set architecture families; GPUs have something analogous to this. PTX is the name for a family of recent Nvidia GPU instruction set architectures; other brands (and older models) have different architectures . You can read the GPU machine language documentation at Nvidia's PTX ISA reference. That PTX architecture coexists as the compute architecture implementation, in tandem with Nvidia's graphics architecture implementation. Much of the actual digital circuitry of the GPU is shared between these two programming models, even though the PTX ISA exposes a different software-abstraction than an ordinary graphics processor state machine. PTX is more accessible, because better public documentation exists, compared to most GPU "graphics" instruction sets.

OpenGL itself is a "common subset" of higher level functions, as BenRG correctly described earlier. The code that OpenGL generates for your CPU will consist of commands to set up and manipulate the internal state-machine of the software-abstraction model for the graphics processor: the CPU will run code to write (e.g.) memory mapped I/O for control registers, data buffers, DMA accelerator hardware that copies data, and so on - shuffling data and workloads to the GPU and waiting for the GPU to report when the work completes. These GPU workloads take the form of executable programs targeted for the specific GPU instruction set, generated at compile-time or at run-time (depending on your operating system and hardware drivers). Nimur (talk) 05:45, 15 September 2014 (UTC)[reply]

A call like glFoo(x, y); compiles into something like push y; push x; call glFoo; add esp, 8, like an ordinary function call. The implementation of glFoo is OS-specific, and I don't know how it works on any OS, but probably it uses a system call like ioctl to pass the data to the video driver in the kernel. It may store the data from each call in a user-mode buffer and pass several commands at once to the kernel for better speed (given that OpenGL uses one function call per vertex). -- BenRG (talk) 17:20, 15 September 2014 (UTC)[reply]

Mandatory recursion?

So, I've come across a few pages saying that certain problems must be computed recursively (the Ackermann function, for example), and maybe it's mathematicians using the term recursion differently from how I've encountered it in programming or something but that doesn't make much sense to me. In the end the program just gets turned into conditional jumps when it's compiled. Can someone explain? Horselover Frost (talk · edits) 17:01, 15 September 2014 (UTC)[reply]

Are you sure they didn't say that it isn't primitive recursive? In theoretical CS, "recursive function" is basically synonymous with "computable function". You can of course always translate a recursive solution to a problem into an iterative solution with an array in place of the stack, and vice versa. Optimizing compilers actually turn imperative flow control into recursive tail calls in their intermediate code representation (see SSA is Functional Programming), and high-performance CPUs take a rather functional approach to executing the machine code (see out-of-order execution). -- BenRG (talk) 18:28, 15 September 2014 (UTC)[reply]

To quote one of the pages: "Interestingly enough, the Ackermann function is one of the very few known examples of function that can only be implemented recursively. It is impossible to implement it with just for loops and other control flow commands." I suspect this is just a bad explanation that's confusing me. Horselover Frost (talk · edits) 19:37, 15 September 2014 (UTC)[reply]

Right, so there's a kernel of truth here, but as you say, it's badly explained.

Because the function is not primitive recursive, you can't compute it using just for loops used in their usual form (that is, where a counter variable counts up to a limit that has already been computed by the time you hit the for statement, and where you don't change the value of the variable inside the loop.

As BenRG explains, though, that doesn't mean you have to use recursion per se. You could do it with a while loop, for example. --Trovatore (talk) 19:55, 15 September 2014 (UTC)[reply]

(EC) I think you're right, that the word 'recursive' can mean slightly different things to a pure mathematician and a theoretical computer scientist. As Ben says, in CS, all computable functions are in some sense recursive functions. See e.g. Recurrence_relation, which is often what a mathematician means when we say things like "foo is defined recursively," and this also applies to the Ackermann function. While some recurrence relations can be 'solved' to yield a value X_n+1 without previously computing X_n, the Ackermann function is not one of those. I may be missing something, but I think the quote you've pulled is nonsense. I'm pretty sure I could implement a computation of A(m,n) using "for loops and other control flow commands" -- I'd just compute A(1,1), A(0,0), etc before calculating e.g. A(1,2) -- but again, I may be missing something in the terminology... do they consider "while" to be normal flow control? What about using a for loop with a range that is variable? Btw, in case anyone else wants to look into it, your quote seems to be from here [1], not our WP article. SemanticMantis (talk) 20:01, 15 September 2014 (UTC)[reply]

That's got to be it. I can write a simulation of (say) an 8086 CPU that doesn't use recursion...so emulating a computer that's doing recursion doesn't require recursion. That means that I can turn any recursive function into a non-recursive program that's emulating a recursive program.

More directly, any program that's doing recursion is merely using the stack to remember where it's got to in the recursive processing sequence. Remembering that data, and correctly acting on it - but in some other way - can always avoid doing recursion.

However, mathematicians do indeed talk about 'recursive' functions as something special. I'm pretty sure that there must be a subtle difference in how computer programmers and mathematicians are using the word.

SteveBaker (talk) 02:25, 16 September 2014 (UTC)[reply]

I thought that was well enough explained already? To recap, to a mathematician (well, mathematical logician), "recursive function" is synonymous with computable function. It doesn't mean you have to use recursion, just that you don't need something stronger than recursion (for example, an oracle). --Trovatore (talk) 19:51, 16 September 2014 (UTC)[reply]

I searched the web for the quoted sentences and found http://rosettacode.org/wiki/Ackermann_function, which cites this Youtube video, which may be the source of the problem. Although the host seems very professorial, and is actually a professor, he's not a professor of theoretical CS (as he admits part way though), and unfortunately it shows—the whole video seems like his confused recollections of something he read about a long time ago. I skimmed his video about data compression and it's the same. I don't know why they didn't find someone with relevant expertise to make these things. -- BenRG (talk) 17:26, 16 September 2014 (UTC)[reply]

Facebook friends

On my timeline, there are entries where Facebook shows 9 squares, the first eight show my friends' profil pictures and the last square says "+number". This is not my friends list, it's an additional entry. Apparently, it says how many friends I gained in 2011 and 2012. And the friends in those square always stay the same. How can you remove this from the timeline? It could be a bug resulted from the timeline's introduction of Facebook. There are no options for this entry and when I click on the heading, it leads me to all my current friends. --2.245.209.170 (talk) 18:24, 15 September 2014 (UTC)[reply]

How to find (list) all folders without any .wpl-file in them? (Windows7)

Resolved

I have a lot of files (both mp3 audio and other non-audio files) spread across various folders.
Question: Is there some way, in MicrosoftWindows7, to list the full path names of all the folders that do not contain any file with the extention: .wpl ?
--46.15.97.102 (talk) 20:48, 15 September 2014 (UTC)[reply]

There may be a Windows method, but I'd install cygwin, then use ls and grep. Some details given with this relevant question on grep [2]. SemanticMantis (talk) 22:01, 15 September 2014 (UTC)[reply]

I am rather "computer illiterate", so I want to avoid installing anything (cygwin).
Question 2: Is it possible to do what you are suggesting by using grepWin instead? ("grepWin is a simple search and replace tool which can use regular expressions to do its job.") (http://portableapps.com/apps/utilities/grepwin-portable)
-- (OP) 178.232.3.203 (talk) 04:43, 16 September 2014 (UTC)[reply]

You could run cmd.exe and type this:

   for /r D:\foo %i in (.) do @if not exist "%i\*.wpl" echo %i

but replacing D:\foo with the path of the topmost folder you want to search. -- BenRG (talk) 06:03, 16 September 2014 (UTC)[reply]

@ BenRG: Perfect! Thank you! :-)
-- (OP) 46.212.137.120 (talk) 03:37, 17 September 2014 (UTC)[reply]

Not the OP, but thanks for the answer. For educational purposes, anyone care to spell out what that command does and why? (I think I get it, but don't want to pollute with bad answers). To the OP:, yes, grepWin could also work, but BenRG's command is probably less hassle for you, since it seems it will work "out of the box". SemanticMantis (talk) 13:51, 16 September 2014 (UTC)[reply]

for /r [directory] %[variable] in (.) do [command] iterates over subdirectories of [directory] executing [command] with the directory path substituted for %[variable], as described here, @ stops for from printing each substituted command before executing it, and if not exist [path] [command] executes [command] only if no file/directory matching [path] exists, as described here. I'm not sure it's worth learning cmd.exe, though, because it's not very useful unless you happen to be doing something that fits its limited capabilities. It might be worth learning Windows PowerShell, but I never got around to it. -- BenRG (talk) 16:54, 16 September 2014 (UTC)[reply]

@ SemanticMantis: Question 3: Even though BenRG's solution works perfectly, I am still curious about how I could do the same thing using grepWin…
Would you (SemanticMantis) care to show and (very) briefly explain the grepWin solution too ? Please ;-)
-- (OP) 46.212.137.120 (talk) 03:37, 17 September 2014 (UTC)[reply]

If this screenshot accurately represents grepWin's capabilities, then I don't think it can be done, because it isn't one of the fixed functions that the author chose to include. Despite its name, "grepWin" seems to be totally different from the grep utility that SemanticMantis suggested you use. Actually, though, I don't see how to solve this particular problem with ls and grep either. -- BenRG (talk) 15:40, 17 September 2014 (UTC)[reply]

Yes, grepWin is totally different from the grep utility.
What it would need is an advanced Regular expression that match the name of every folder which does not have any file ending in ".wpl" or ".wpl.txt" inside it.
And the book: Programming Perl, also known as The Camel Book, published by O'Reilly Media, which I have been told delves deeply into the mysteries of Regular expressions, sadly, seems far too difficult for me to get through ;-(
I believe the results list from grepWin would be doubleclickable and thus would save me a lot of hassle getting into (opening) the folders I have found.
Therefore I am hoping that some RegExp-guru here on the Refdesk, maybe could provide. :-)
-- (OP) 178.232.156.142 (talk) 23:11, 17 September 2014 (UTC)[reply]

You're definitely going to need more than just regular expressions.

What regular expressions do is match patterns in text.

But you're interested in listing directories, and discovering which directories do or don't have certain files you're interested in. There's no regular expression in the world that can do that all by itself (although regular expressions might play a role in the eventual, composite solution).

You're going to need a tiny little program, like the one BenRG showed. —Steve Summit (talk) 02:23, 18 September 2014 (UTC)[reply]

Oh I see. (I mistakenly believed that nearly all the capabilities of the programming language Perl lay within the scope of Regular expressions). Thanks for enlightening me! :-)
And thanks again to BenRG and SemanticMantis! :-)
-- (OP) Seren-dipper (talk) 14:49, 19 September 2014 (UTC)[reply]